mess

Mess

== include(page="template/taskheader" task_id="mess") ==

Poveste şi cerinţă...

Ţi-ai cumpărat un telefon mobil nou şi primul lucru pe care l-ai făcut a fost să intri pe messenger. Lista de messenger e mai bizară: este formată din numere (fiecărui utilizator din lista de messenger $i$ s-a asociat un număr din intervalul $[1,1 000 000 000]$) şi nu este sortată.
 
Iniţial toţi utilizatorii sunt online (un alt lucru ciudat) şi pe parcurs unii utilizatori ies / intră pe messenger.
Mai concret se dă vectorul iniţial cu $N$ numere (utilizatorii din lista ta de messenger), apoi o succesiune de $M$ operaţii.
Operaţiile sunt de două tipuri:
 
* $1 p =$ utilizatorul de pe poziţia p din listă îşi schimbă starea (din online devine offline şi invers).
* $2 p q k =$ vrei să afli care este al $k$-lea utilizator online (în ordine crescătoare) din intervalul $[p,q]$, unde $p$ şi $q$ sunt poziţii din vector, $p≤q$.
 
Scrieţi un program care să răspundă la operaţiile de tip $2$.

h2. Date de intrare

Fişierul de intrare $mess.in$ ...

Fişierul de intrare $mess.in$ va conţine pe prima linie două numere naturale $N M$ reprezentând numărul de utilizatori din listă, respectiv numărul de operaţii ce vor fi efectuate. Pe următoarea linie se află $N$ numere naturale separate prin spaţii reprezentând utilizatorii din lista de messenger. Pe următoarele $M$ linii se află câte o operaţie, în formatul specificat în enunţ.

h2. Date de ieşire

În fişierul de ieşire $mess.out$ ...

Fişierul de ieşire $mess.out$ va conţine răspunsurile la operaţiile de tip $2$, câte unul pe fiecare linie, în ordinea din fişierul de intrare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 100 000$
* Pentru $30%$ din teste $N, M ≤ 20 000$
* Utilizatorii sunt numerotaţi cu numere naturale din intervalul $[0, 1 000 000 000]$
* Se garantează că la fiecare operaţie de tip $2$ există cel puţin $k$ utilizatori online în acel interval.
* Lista conţine numere distincte.
* Poziţiile din vector sunt numerotate de la $1$ la $N$.

h2. Exemplu
table(example). |_. mess.in |_. mess.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10 9
3 15 6 2 10 7 80 4 1 9
1 9
1 3
2 6 7 2
2 5 7 1
1 6
2 2 3 1
1 5
2 1 9 3
2 4 9 3
| 80
7
15
4
80

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="mess") ==

8914