Description

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.

Input Format

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.

Output Format

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

4 9
1 3 2
0 0 4 2
3 1 1
0 2 4 3
3 3 1
0 4 4 4
3 5 1
2 6 1 4
1 7 4
3 8 1

0
0
4
4

Hint

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