题目描述

A new DJ is in town. DJ Darko needs to set up his speakers. He has $N$ speakers in a row with the $i$-th speaker volume set to $A_i$. Changing the volume is rather difficult so the $i$-th speaker requires $B_i$ units of energy to increase or decrease the volume by the value of 1.

Unfortunately, Darko's evil twin brother Karko likes to mess with him. There are $Q$ events that will be happening.

1 l r x

2 l r

In an event of type 1, Karko changes the volume of all speakers from the $l$-th to the $r$-th by $x$. In an event of type 2, Darko sets all the speakers from the $l$-th to the $r$-th to the same volume in a way that uses up the minimal amount of energy. If there are multiple ways of doing that, he chooses the one which minimizes the final volume.

As a bystander, you would like to know the volume that Darko set for each event of type 2.

输入格式

The first line contains the number of speakers $N$ and the number of events $Q$. In the second line, there are $N$ numbers $A_i$ indicating the current volume of the speakers. In the third line, there are $N$ numbers $B_i$, indicating the energy needed to change the volume of the $i$-th speaker by one. In the next $Q$ lines there are $Q$ events, formatted in the way described above. All numbers in the input are integers.

输出格式

For each event of type 2, output the volume to which Darko set the speakers.

5 5
8 1 6 4 9
3 6 4 1 7
2 2 4
1 1 4 -8
2 1 1
2 1 3
2 4 5

1
0
-7
9

8 3
4 3 9 3 7 6 4 8
9 5 8 5 2 2 1 8
1 1 7 -10
2 5 5
2 4 7

-3
-7

提示

Input limits

• $1 \leq N, Q \leq 200\,000$
• $0 \leq A_i, B_i \leq 10^9$
• $1 \leq l \leq r \leq N$
• $-10^9 \leq x \leq 10^9$