Ţ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.

Cerinţă

Scrieţi un program care să răspundă la operaţiile de tip 2.

Date de intrare

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ţ.

Date de ieşire

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.

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.

Exemplu

mess.in	mess.out
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

stud. Mircea Dima

Universitatea Bucureşti

blasterzm@gmail.com