406738: GYM102512 G Honeymoon

Yamada and Shiraishi are planning a honeymoon trip. They have looked at $$$N$$$ tourist destinations, numbered from $$$1$$$ to $$$N$$$. The $$$i$$$-th tourist destination increases Yamada's happiness value by $$$a_{i}$$$ and Shiraishi's happiness value by $$$b_{i}$$$.

A trip consists of visiting the tourist destinations $$$l, l+1,..., r$$$ in order, one per day. Initially, both of their happiness values are $$$0$$$. After every day of the trip, they compute their combined happiness for the day, which is the maximum of both of their current happiness values (because Yamada is happy if Shiraishi is happy and vice versa). Finally, the total happiness of the trip is the sum of their combined happiness over all $$$r-l+1$$$ days (see the samples for an example).

Yamada and Shiraishi made $$$Q$$$ possible trip plans. The $$$i$$$-th plan consists of them visiting the tourist destinations from $$$l_{i}$$$ to $$$r_{i}$$$ in this order. Can you help them calculate the total happiness of each plan?

The first line of input contains two space-separated integers, $$$N, Q$$$ ($$$1 \le N, Q \le 500000$$$).

The next line of input contains $$$N$$$ space-separated integers, denoting the values $$$a_{i}$$$ ($$$-10^{6} \le a_{i} \le 10^{6}$$$).

The next line of input contains $$$N$$$ space-separated integers, denoting the values $$$b_{i}$$$ ($$$-10^{6} \le b_{i} \le 10^{6}$$$).

The next $$$Q$$$ lines of input contain $$$2$$$ space-separated integers each. The $$$i$$$-th such line contains the values $$$l_{i}, r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le N$$$).

Output $$$Q$$$ lines containing a single integer each: the total happiness of each plan.

Subtask 1 (4 points): $$$N, Q \le 5000$$$

Subtask 2 (7 points): $$$N, Q \le 150000, a_{i} \ge 0, b_{i} = 0$$$ for all $$$1 \le i \le N$$$

Subtask 3 (21 points): $$$N, Q \le 150000, b_{i} = 0$$$ for all $$$1 \le i \le N$$$

Subtask 4 (37 points): $$$N, Q \le 150000$$$

Subtask 5 (31 points): No additional constraints

6 7
3 -5 8 -10 3 7
-4 20 9 -100 105 20
1 6
1 5
2 4
3 3
3 6
2 5
4 5

120
70
42
9
55
76
-5

1 1
-110
318
1 1

318

Consider the first trip of the first sample.

Before the trip starts: Yamada's happiness = $$$0$$$, Shiraishi's happiness = $$$0$$$.

After day $$$1$$$: Yamada's happiness = $$$3$$$, Shiraishi's happiness = $$$-4$$$, Combined happiness = $$$3$$$.

After day $$$2$$$: Yamada's happiness = $$$3-5=-2$$$, Shiraishi's happiness = $$$-4+20=16$$$, Combined happiness = $$$16$$$.

After day $$$3$$$: Yamada's happiness = $$$-2+8=6$$$, Shiraishi's happiness = $$$16+9=25$$$, Combined happiness = $$$25$$$.

After day $$$4$$$: Yamada's happiness = $$$6-10=-4$$$, Shiraishi's happiness = $$$25-100=-75$$$, Combined happiness = $$$-4$$$.

After day $$$5$$$: Yamada's happiness = $$$-4+3=-1$$$, Shiraishi's happiness = $$$-75+105=30$$$, Combined happiness = $$$30$$$.

After day $$$6$$$: Yamada's happiness = $$$-1+7=6$$$, Shiraishi's happiness = $$$30+20=50$$$, Combined happiness = $$$50$$$.

The total happiness of the trip is $$$3+16+25-4+30+50=120$$$.

For the third query, the combined happiness for the three days are $$$20, 29, -7$$$ respectively, with a total happiness of $$$20+29-7=42$$$.