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

Poveste şi cerinţă...

La grădiniţa din centrul oraşului Suceava există $N$ copii, numerotaţi de la $0$ la $N–1$. Primarul le face o vizită şi a hotărât să împartă copiilor biluţe. Astfel, el are un sac mare plin cu bile ce au inscripţionat pe ele câte un număr natural. Din când în când primarul mai pune întrebări copiilor cu privire la bilele pe care le-au primit. Iată ce operaţii poate efectua primarul:
 
* dăruieşte tuturor copiilor cu numere din intervalul $[a,b]$ câte o bilă inscripţionată cu numărul $p$
* îi întreabă care ar fi numărul inscripţionat pe cea de-a $k$-a bilă din şirul format din bilele copiilor din intervalul $[a,b]$, ştiind că bilele sunt aşezate în ordinea crescătoare a numerelor inscripţionate pe ele; dacă nu există $k$ bile în intervalul $[a,b]$, răspunsul va fi $-1$
 
Ajutaţi-i pe copii să răspundă la întrebările primarului.

h2. Date de intrare

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

Pe prima linie a fişierului $bile4.in$ se găseşte un număr natural $N$, reprezentând numărul de copii. Pe următoarea linie se găseşte un număr natural $M$, reprezentând numărul de operaţii efectuate de primar. Pe următoarele $M$ linii sunt descrise operaţiile pe care le efectuează primarul, câte o operaţie pe o linie.  O linie care descrie o operaţie poate avea unul dintre următoarele două formate:
 
table(example). |_. Format |_. Explicatie |
| 1 a b p | descrie o operaţie de tip 1 (primarul va da tuturor copiilor din intervalul [a,b] câte o bilă
inscripţionată cu numărul natural  p) |
| 2 a b k | descrie o operaţie de tip 2 (primarul îi întreabă pe copii care este numărul inscripţionat pe cea
de-a k-a bilă din şirul format din bilele copiilor din intervalul [a,b], ştiind că bilele sunt
 aşezate în ordinea crescătoare a numerelor inscripţionate pe ele)
|

h2. Date de ieşire

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

În fişierul $bile4.out$ veţi afişa câte o linie pentru fiecare operaţie de tipul $2$ din fişierul de intrare. Pe cea de a $i$-a linie va fi scris un număr întreg care reprezeintă răspunsul pentru cea de-a $i$-a operaţie de tip $2$ din fişierul de intrare.

h2. Restricţii

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

* $1 ≤ N ≤ 30000$
* $1 ≤ M ≤ 30000$
* $1 ≤ numărul inscripţionat pe bile ≤ 30000$
* $un copil poate avea mai multe bile, eventual de aceeaşi valoare$
* $în urma unei operaţii de tip 2, configuraţia bilelor rămâne neschimbată$
* $iniţial toţi copii au 4 bile$

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

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

| 10
10
1 8 9 5
1 6 6 2
2 8 8 1
2 5 7 1
1 6 7 2
2 1 8 3
2 6 7 1
2 5 5 1
1 9 9 1
2 7 8 1
| 5
2
2
2
-1
2

|

h3. Explicaţie
 
...
 

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