A fost război, valorile s-au răsturnat, atacurile cu mâna armată au devnit o normalitate, aşa că gestiunea situaţiei Bucureştiului a devenit o problemă fundamentală consumatoare de timp - Comisarii vă cer ajutorul în scrierea unui program care să automatizeze următoarele operaţii:
* În urma unor evenimente importante (precum jefuirea Bijuteriei Lembert) importanţa unei figuri se modifică - _1 pos val_ - importanţa celui de-al _pos_-ulea criminal de pe listă devine _val_.
* _2 val_ - Comisarii vor să ştie **dacă** ar fi să elimine începând cu gangsterul de pe poziţia _pos_, folosind metoda menţionată, câţi mafioţi ar fi suprimaţi?
* În urma unor evenimente importante (precum jefuirea Bijuteriei Lembert) importanţa unei figuri se modifică - $1 pos val$ - importanţa celui de-al $pos$-ulea criminal de pe listă devine $val$.
* $2 val$ - Comisarii vor să ştie **dacă** ar fi să elimine începând cu gangsterul de pe poziţia $pos$, folosind metoda menţionată, câţi mafioţi ar fi suprimaţi?
h2. Date de intrare
Pe prima linie a fisierului de intrare **cumainilecurate.in** se afla doua numere intregi **N** si **M**, separate printr-un spatiu, semnificand numarul de gangsteri de pe lista primita si respectiv numarul de interogari.
Pe a doua linie se afla **N** numere intregi pozitive separate prin cate un spatiu, reprezentand importanta fiecarui mafiot de pe lista, in ordine.
Urmatoarele **M** linii au fiecare una din structurile _1 pos val_ sau _2 pos_, cu semnificatiile din enunt.
Pe prima linie a fisierului de intrare $cumainilecurate.in$ se afla doua numere intregi $N$ si $M$, separate printr-un spatiu, semnificand numarul de gangsteri de pe lista primita si respectiv numarul de interogari.
Pe a doua linie se afla $N$ numere intregi pozitive separate prin cate un spatiu, reprezentand importanta fiecarui mafiot de pe lista, in ordine.
Urmatoarele $M$ linii au fiecare una din structurile $1 pos val$ sau $2 pos$, cu semnificatiile din enunt.
h2. Date de ieşire
Fisierul **cumainilecurate.out** trebuie sa contina atatea linii cate operatii de tipul 2 sunt in fisierul de intrare, fiecare linie reprezentand raspunsul pentru operatia de tipul 2 corespunzatoare din input.
Fisierul $cumainilecurate.out$ trebuie sa contina atatea linii cate operatii de tipul $2$ sunt in fisierul de intrare, fiecare linie reprezentand raspunsul pentru operatia de tipul $2$ corespunzatoare din input.
h2. Restricţii
* 1 ≤ **N** ≤ 10^5^
* 1 ≤ **M** ≤ 6 * 10^4^
* 1 ≤ _importanta unui mafiot_ ≤ 10^9^
* $1 ≤ N ≤ 10^5^ $
* $1 ≤ M ≤ 6 * 10^4^ $
* $1 ≤ importanta unui mafiot ≤ 10^9^ $
* **Atentie!** Volum mare de date de intrare, vă recomandăm să optimizaţi citirea folosindu-va de "acest cod":http://pastebin.com/kSM2CRBq.
* **Subtask 1 (20 puncte)**: 1 ≤ **N** ≤ 3000 si 1 ≤ **M** ≤ 2000
* **Subtask 2 (20 puncte)**: Se garanteaza ca in input vor fi cel mult 10 operatii de _tipul 1_.
* **Subtask 1 (20 puncte)**: $1 ≤ N ≤ 3000$ si $1 ≤ M ≤ 2000$
* **Subtask 2 (20 puncte)**: Se garanteaza ca in input vor fi cel mult $10$ operatii de tipul $1$.
* **Subtask 3 (60 puncte)**: Restrictii initiale
h2. Exemplu
h3. Explicaţie
Pentru primele 5 interogari acestia sunt gangsterii alesi:
**1** **5** 3 4 2 _(aici se vede clar ca strategia calculata a comisarilor nu este chiar cea mai buna, varianta optima fiind, de fapt, **1** 5 **3** **4** 2)_
1 **5** 3 4 2
1 5 **3** **4** 2
1 5 3 **4** 2
1 5 3 4 **2**
$**1** **5** 3 4 2$ _(aici se vede clar ca strategia calculata a comisarilor nu este chiar cea mai buna, varianta optima fiind, de fapt, $**1** 5 **3** **4** 2$)_
$1 **5** 3 4 2$
$1 5 **3** **4** 2$
$1 5 3 **4** 2$
$1 5 3 4 **2**$
Dupa modificarea importantei mafiotului cu numarul de ordine 2, lista arata in felul urmator:
**1 2 3 4 2**
