P6794 [SNOI2020] Pool

There is a long, narrow pool that can be divided into $n$ cells. Cell $i$ and cell $i+1$ are adjacent, separated by an adjustable barrier with height $h_i$. To the left of cell $1$ and to the right of cell $n$ are infinitely high pool walls. Initially, there is no water in the pool. Now perform $q$ operations. There are four types of operations: - `0 i x h`: Pour water into cell $x$ until the water surface height in that cell is not less than $h$ (if the current water surface height is already at least $h$, nothing happens). - `1 i x`: Open the drain at the bottom of cell $x$ until the water in that cell is completely drained, then close the drain. - `2 i x h`: Increase the height of the barrier to the right of cell $x$ to $h$ (do not change existing water levels; it is guaranteed that the barrier height will not decrease). - `3 i x`: Query the water surface height in cell $x$. Here, $i$ means that this operation is based on the state after the $i$-th operation; $i=0$ means it is based on the initial state. In other words, the operations need to be persistent.

The first line contains two non-negative integers $n,q$, representing the number of cells in the pool and the number of operations. The next line contains $n-1$ positive integers $h_i$, representing the initial heights of the barriers. Then follow $q$ lines, each describing one operation.

For each operation of type `3`, output one line with one integer representing the answer.

#### Sample Explanation For sample $1$:  #### Constraints For all testdata, $1\le n,q\le 2\times 10^5$, $0\le h_i\le 10^9$. - For $10\%$ of the testdata, $n \le 500$. - For another $20\%$, there is no operation `1`, and $i$ increases consecutively starting from $0$ (persistence is not needed). - For another $20\%$, there is no operation `1`. - For another $20\%$, and $i$ increases consecutively starting from $0$ (persistence is not needed). - For the remaining $30\%$ of the testdata, there are no special restrictions. Translated by ChatGPT 5