There is a long, narrow pool that can be divided into $n$ cells. The $i$-th cell and the $(i+1)$-th cell are adjacent, separated by an adjustable partition of height $h_i$. The left side of the first cell and the right side of the $n$-th cell are walls of infinite height. Initially, there is no water in the pool. There are $q$ operations, which are of the following four types:

• 0 i x h: Fill the $x$-th cell with water until the water level in that cell is at least $h$ (if the current water level is already at least $h$, nothing happens);
• 1 i x: Open the drain at the bottom of the $x$-th cell until the cell is empty, then close the drain;
• 2 i x h: Increase the height of the partition to the right of the $x$-th cell to $h$ (this does not change the existing water level, and it is guaranteed that the partition height will not decrease);
• 3 i x: Query the water level of the $x$-th cell.

Here, $i$ indicates that the operation is based on the state after the $i$-th operation, where $i=0$ represents the initial state. In other words, this problem requires the operations to be persistent.

Input

The first line contains two natural numbers $n$ and $q$, representing the number of cells and the number of operations.

The next line contains $n-1$ positive integers $h_1, h_2, \dots, h_{n-1}$, representing the initial heights of the partitions.

The next $q$ lines each contain a positive integer representing an operation.

Output

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

Examples

Input 1

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

Output 1

0
0
4
4

Note

Subtasks

For all data, $1\le n,q\le 2\times 10^5, 0\le h_i\le 10^9$.

• For $10\%$ of the data, $n\le 500$;
• For another $20\%$, there is no operation $1$, and $i$ increases consecutively starting from $0$ (persistence is not required);
• For another $20\%$, there is no operation $1$;
• For another $20\%$, $i$ increases consecutively starting from $0$ (persistence is not required);
• For the remaining $30\%$ of the data, there are no special restrictions.