DJ Darko

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$.

Unforutanently, 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.

• $1 ≤ N, Q ≤ 200\\,000$
• $0 ≤ A\_i , B\_i ≤ 10^9$
• $1 ≤ l ≤ r ≤ N$
• $-10^{9} ≤ x ≤ 10^9$