410064: GYM103934 L Cris's vacations in Cairo

After a semester of hard work, Cris took some days off and decided to spend them in Cairo, Egypt. The money she took there is all in Brazilian reals and US dollars, hence she usually has to do exchange operations between Egyptian pounds and these currencies.

The exchange operations that Cris does can be described by an integer $$$X$$$. If $$$X > 0$$$, she sells $$$X$$$ (dollar or real) coins for Egyptian pounds. If $$$X < 0$$$, she buys $$$X$$$ (real or dollar) coins using Egyptian pounds. If $$$X = 0$$$, she does nothing. We call profit the result of the exchange operation in Egyptian pounds. Notice that, when the exchange operation is buying (dollar or real) coins, the profit is a negative value.

Cris got access to the exchange values of the next $$$n$$$ days of a currency exchange house in Alexandria. In the $$$i$$$-th day, the dollar value in Egyptian pounds is $$$d_i$$$ and the Brazilian real value in Egyptian pounds is $$$r_i$$$. In this currency exchange house, the exchange value is the same for selling and buying Egyptian pounds. This is, if in a given day the Brazilian real value is 5 Egyptian pounds, then it's possible to sell 10 reals for 50 Egyptian pounds and it's also possible to buy 10 reals with 50 Egyptian pounds.

Since the currency exchange house is not in the city where Cris is living, she uses her visits to that other city to make the exchange operations that she needs. However, she doesn't want to spend more that one day with the bureaucracy of such transactions. Therefore, if she were to visit Alexandria between days $$$s$$$ and $$$e$$$, she just will do exchange operations in exactly one of those days.

Choosing a day that would maximize the profit of the transactions is a simple task for Cris but, due to her vacations, she asked you to answer $$$q$$$ queries of this kind for her

• $$$s$$$ $$$e$$$ $$$D$$$ $$$R$$$: what is the biggest profit that could be obtain doing exchange operations of $$$D$$$ dollars and $$$R$$$ reals in exactly one day $$$i$$$, $$$s \leq i \leq e$$$.

The first line has two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$).

The second line has $$$n$$$ different integers $$$d_i$$$ ($$$1 \leq d_i \leq 10^9$$$), the value of the dollar in Egyptian pounds on day $$$i$$$.

The second line has $$$n$$$ different integers $$$r_i$$$ ($$$1 \leq r_i \leq 10^9$$$), the value of the Brazilian real in Egyptian pounds on day $$$i$$$.

The next $$$q$$$ lines have queries of the form $$$s$$$ $$$e$$$ $$$D$$$ $$$R$$$ ($$$1 \leq s \leq e \leq n$$$ e $$$-10^9 \leq D, R \leq 10^9$$$) as described in the statement.

Print $$$q$$$ lines, each one of these with the answer of the queries in the order they appear in the input.

3 4
1 4 3
1 1 3
1 3 1 1
1 2 3 1
2 3 -1 -1
1 3 -2 0

6
13
-5
-2