Persistent Water Pool Simulation

You are given a long water pool divided into \(n\) cells (segments). Between each adjacent pair of cells \(i\) and \(i+1\) there is an adjustable board with an initial height \(h_i\). The left side of cell 1 and the right side of cell \(n\) are bounded by walls of infinite height. Initially, there is no water in any cell.

You need to process \(q\) operations. Each operation is based on a previous state identified by an index \(i\) (with \(i = 0\) referring to the initial state) and then a new state is created. The operations are as follows:

• 0 i x h: Based on the state after operation \(i\), pour water into cell \(x\) until the water surface height in that cell is at least \(h\) (if it is already at least \(h\), do nothing). In this problem, the water in each cell is maintained independently.
• 1 i x: Based on the state after operation \(i\), open the drainage at the bottom of cell \(x\) until the cell becomes dry (water height becomes 0), and then close the drainage.
• 2 i x h: Based on the state after operation \(i\), increase the height of the board on the right side of cell \(x\) to \(h\) (the board height will never decrease; if it is already at least \(h\), do nothing). Note that this operation does not change the current water levels.
• 3 i x: Based on the state after operation \(i\), output the water surface height in cell \(x\).

Input Format:

• The first line contains two integers \(n\) and \(q\): the number of cells and the number of operations.
• The second line contains \(n-1\) integers: the initial heights of the boards between cells 1 and 2, 2 and 3, \(\ldots\), \(n-1\) and \(n\).
• The following \(q\) lines each describe an operation in one of the four formats described above. Operations are numbered from 1 to \(q\) in the order they are given. When an operation specifies a base state index \(i\), it refers to the state after the \(i\)-th operation (with \(i=0\) representing the initial state).

Output Format:

• For each query operation (type 3), output the water surface height in the specified cell on a separate line.

Note: In this problem, the water in each cell is maintained independently (i.e. there is no water flow or equalization between adjacent cells), and the operations are persistent: each operation creates a new state based on a previous state.

inputFormat

The input begins with two integers \(n\) and \(q\). The next line contains \(n-1\) integers representing the initial board heights. Each of the following \(q\) lines represents an operation in one of the following formats:

• 0 i x h
• 1 i x
• 2 i x h
• 3 i x

It is guaranteed that there are at least 3 test cases in the set.

outputFormat

For each operation of type 3, output one integer on a new line indicating the water surface height in the queried cell.

sample

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

3
0