長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる。以下のクエリを実行するプログラムを書け。
1 i: $A_i$ を出力する。($1 \le i \le N$)2 x y t: $A_x, A_{x+1}, \ldots, A_y$ の中に $t$ より小さい数が存在する場合、このクエリを無視する。そうでない場合、$A_x, A_{x+1}, \ldots, A_y$ のそれぞれから $t$ を引く。($1 \le x \le y \le N$, $1 \le t \le 10^{18}$)3 x y t: $x \le i \le y$ なるすべての $i$ について、$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: $x \le i \le y$ なるすべての $i$ について、$A_i = \lfloor \sqrt A_i \rfloor$ と設定する。($1 \le x \le y \le N$)
入力
1 行目には $N$ と $Q$ が与えられる。$N$ は数列の長さ、$Q$ はクエリの数を表す。($1 \le N \le 100{,}000$, $1 \le Q \le 500{,}000$)
2 行目には $A_1, A_2, \ldots, A_N$ が与えられる。($1 \le A_i \le 10^{18}$)
続く $Q$ 行には、上述の形式で各クエリが 1 行に 1 つ与えられる。
出力
タイプ 1 i のクエリごとに、結果を 1 行ずつ順に出力せよ。