P11896 "LAOI-9" This Seat of Konata

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.

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

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

### 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**. | Subtask ID | $n\le$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | | $0$ | $2\times 10^3$ | None | $15$ | | $1$ | $10^5$ | There are no noise-reduction devices at any time | $20$ | | $2$ | $10^5$ | There is no operation $3$ | $10$ | | $3$ | $10^5$ | All $a_i$ are the same | $15$ | | $4$ | $10^5$ | None | $40$ | 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