Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. Write a program that executes the following queries:
1 i: Output $A_i$. ($1 \le i \le N$)2 x y t: If there exists a number less than $t$ among $A_x, A_{x+1}, \ldots, A_y$, ignore this query. Otherwise, subtract $t$ from each of $A_x, A_{x+1}, \ldots, A_y$. ($1 \le x \le y \le N$, $1 \le t \le 10^{18}$)3 x y t: For all $x \le i \le y$, set $A_i = t + i - y$. ($1 \le x \le y \le N$, $t - y + x \ge 0$, $1 \le t \le 10^{18}$)4 x y: For all $x \le i \le y$, set $A_i = \lfloor \sqrt A_i \rfloor$. ($1 \le x \le y \le N$)
Input
The first line contains two integers $N$ and $Q$, the length of the sequence and the number of queries. ($1 \le N \le 100{,}000$, $1 \le Q \le 500{,}000$)
The second line contains $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^{18}$)
The following $Q$ lines each contain one query as described above.
Output
For each query of type 1 i, output one line with the result in order.