Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Escriba un programa que ejecute las siguientes consultas:
1 i: Imprimir $A_i$. ($1 \le i \le N$)2 x y t: Si existe un número menor que $t$ entre $A_x, A_{x+1}, \ldots, A_y$, ignora esta consulta. En caso contrario, resta $t$ de cada uno de $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: Para todo $x \le i \le y$, establece $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: Para todo $x \le i \le y$, establece $A_i = \lfloor \sqrt A_i \rfloor$. ($1 \le x \le y \le N$)
Entrada
La primera línea contiene dos enteros $N$ y $Q$, la longitud de la secuencia y el número de consultas. ($1 \le N \le 100{,}000$, $1 \le Q \le 500{,}000$)
La segunda línea contiene $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^{18}$)
Las siguientes $Q$ líneas contienen cada una una consulta como se describe arriba.
Salida
Para cada consulta de tipo 1 i, imprime una línea con el resultado en orden.