P13766 [CERC 2021] 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. 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.

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