Problem Description

Konata is eating in a restaurant, and he finds that the person next to him is making a lot of noise.

For the noise made at each seat $k$, the noise received at position $i$ is $\max(0,j-a_k\times\operatorname{abs}(i-k))$, where $a_k$ is the attenuation coefficient of the noise, and $j$ is the initial loudness. The detailed definition is given below.

For the noise at each position, take the maximum value among the noises arriving at this position from all seats.

However, in order to reduce noise, the staff have built noise-reduction devices at some places. If a position $i$ satisfies $b_i=1$, then this position initially has a noise-reduction device. For a noise-reduction device, after the noise reaches the first noise-reduction device it meets on the left and the first one it meets on the right, the attenuation coefficient will become $2$ times the original. Formally, suppose that for the propagation from position $k$ to position $i$, the position of the first noise-reduction device encountered is $x$. Then the noise received at position $i$ is $\max(0,j-a_k\times\operatorname{abs}(k-x)-2a_k\times\operatorname{abs}(i-x))$.

Note: a noise-reduction device only affects noise produced after it is built.

A drawback of the noise-reduction device is that if noise is produced at the same position as the device, then the device at that position will be destroyed immediately, meaning it will not take effect for this noise or any future noises.

Therefore, at certain times, the staff will build new noise-reduction devices at some positions.

Now, within $m$ unit times, at each time there may be one of three events.

• The input format is 1 i j, meaning the person at seat $i$ makes a sound with loudness $j$.

• The input format is 2 i, meaning query the noise received by the person at seat $i$.

• The input format is 3 i, meaning the staff build a new noise-reduction device at position $i$. If this position already has a noise-reduction device, then this operation has no effect. Of course, since a noise-reduction device only affects noise produced after it is built, building a new device at a position that has produced noise before will not cause the device to be destroyed immediately.

Input Format

The first line contains the number of seats $n$ and the number of events $m$.

The second line contains $n$ numbers $a_i$, where $a_i$ is the attenuation coefficient of the noise produced by the person at seat $i$.

The third line contains $n$ numbers $b_i$. If $b_i$ is $1$, it means there is a noise-reduction device at this position; otherwise, there is none.

The next $m$ lines each describe one event.

In each event, the event type is given first. Then $i$ (let $las$ be the last output answer, initially $0$) must be transformed to obtain the real input. $i$ should become $((i+las-1)\bmod n)+1$.

Output Format

For operation $2$, output the answer and print a newline.

3 2
1 1 1
0 0 0
1 1 5
2 3

3

5 5
1 2 3 4 1
1 1 0 0 1
1 1 6
1 2 8
3 1
1 1 10
2 5

6

8 5
1 2 2 1 1 2 3 1
0 0 0 0 0 0 0 0
1 1 3
2 3
3 2
1 2 4
2 5

1
0

Hint

Sample Explanation

For the first $2$ samples, the transformed input is the same as the original input.

For sample $1$, the only contribution comes from the $5$ units of noise produced at position $1$. When it reaches position $3$, the noise is $\max(0,5-(3-1)\times 1)=3$.

This problem uses bundled testdata.

For $100\%$ of the data, $1\le n,m\le 10^5,1\le a_i\le 10^9,b_i\in\{0,1\},1\le i\le n,1\le j\le 10^9$.

Translated by ChatGPT 5