Intervale

Cerință

Se dau $N$ numere naturale și $Q$ întrebări. Asupra numerelor se pot aplica două tipuri de operații:

• Tipul $1$: Se dă intervalul $[L, R]$. Pentru fiecare element $a_i$, cu $L \leq i \leq R$, se aplică operația $a_i \leftarrow \lfloor \sqrt{a_i} \rfloor,$ unde $\lfloor x \rfloor$ reprezintă partea întreagă a numărului real $x$.
• Tipul $2$: Se dă poziția $P$. Se afișează valoarea elementului de la poziția $P$.

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $Q$.
Pe a doua linie se găsesc cele $N$ numere naturale $a_1, a_2, \dots, a_N$.
Pe următoarele $Q$ linii se găsesc întrebările. Fiecare linie începe cu tipul întrebării, iar $tip$ $\in \{1, 2\}$:

• întrebările de tipul $1$ au formatul 1 L R;
• întrebările de tipul $2$ au formatul 2 P.

Date de ieșire

Pentru fiecare întrebare de tipul $2$ se va afișa, pe câte o linie, răspunsul corespunzător.

Restricții și precizări

• $1 \leq N, Q \leq 200 \ 000$
• $0 \leq a_i \leq 1 \ 000 \ 000 \ 000$
• $1 \leq L, R, P \leq N$
• Pentru teste în valoare de 30 de puncte, $N \leq 2 \ 000$
• Pentru teste în valoare de 20 de puncte, $0 \leq a_i \leq 3$

Exemplu

stdin

10 4
7 5 4 8 23 82 101 100 5 1
1 2 9
2 7
1 5 8
2 6

stdout

10
3

Explicație

După prima operație (tipul $1$, intervalul $[2, 9]$), șirul devine: $[$7, 2, 2, 2, 4, 9, 10, 10, 2, 1$]$

A doua operație este de tipul $2$, cu $P = 7$, deci se afișează valoarea de la poziția $7$, adică $10$.

După a treia operație (tipul $1$, intervalul $[5, 8]$), șirul devine: $[$7, 2, 2, 2, 2, 3, 3, 3, 2, 1$]$

Ultima operație este de tipul $2$, cu $P = 6$, astfel se afișează valoarea de la poziția $6$, adică $3$.