nth-root-upd

Tihoi tocmai ce a ajuns la capitolul range queries la informatică. Ca de obicei, profesorul i-a dat o temă, însă din greșeală a incărcat o problemă mai grea. Tihoi vă roagă pe voi să îl ajutați. Aceasta este problema:

Cerință

Se dau un vector cu $n$ elemente si $q$ query-uri. Query-urile pot fi de două tipuri:

• $1$ $st$ $dr$ $a$ $b$ : elementele $v_i$ cu $st \leq i \leq dr$ devin $min( v_i, a \sqrt[b]{i} )$;
• $2$ $poz$ : să se afișeze valoarea elementului de pe poziția $poz$.

Date de intrare

Se citesc de la tastatură $n$ si $q$ urmate de $n$ numere si $q$ query-uri.

Date de ieșire

Se vor afișa rezultatele query-urilor de tip $2$, in ordine, pe câte un rând.

Restricții și precizări

• $1 \leq n, q \leq 200 \ 000$;
• $1 \leq v_i, a, b \leq 200 \ 000$;
• $n, q, v_i, a, b \in \mathbb{N}$.
• Se garantează că toate valorile pot fi reprezentate pe tipurile de date standard din limbajul C++.
• Fie răspunsul concurentului $A$ si răspunsul comisiei $B$. Se admite răspunsul doar dacă $|A-B| < {10}^{-2}.$

Exemplu

stdin

5 3
9 9 9 9 9
1 2 4 3 2
2 3
2 4

stdout

5.196152
6.000000

Explicație

Se poate verifica ușor folosind un calculator că acesta este rezultatul.