bile

La grãdinita din centrul orasului Suceava existã N copii, numerotati de la 0 la N-1. Primarul le face o vizitã si a hotãrât sã împartã copiilor bilute. Astfel, el are un sac mare plin cu bile ce au inscriptionat 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 operatii poate efectua primarul:
1. dãruieste tuturor copiilor cu numere din intervalul [a,b] câte o bilã inscriptionatã cu numãrul p.
2. îi întreabã care ar fi numãrul inscriptionat pe cea de-a k-a bilã din sirul format din bilele copiilor din intervalul [a,b], stiind cã bilele sunt asezate în ordinea crescãtoare a numerelor inscriptionate pe ele; dacã nu existã k bile în intervalul [a,b], rãspunsul va fi -1.

Cerinta
Ajutati-i pe copii sã rãspundã la întrebãrile primarului.

Date de intrare
Fisierul de intrare bile.in contine pe prima linie un numãr natural N, reprezentând numãrul de copii. Pe urmãtoarea linie se afla un numãr natural M, reprezentând numãrul de operatii efectuate de primar. Pe urmãtoarele M linii sunt descrise operatiile pe care le efectueazã primarul, câte o operatie pe o linie. O linie care descrie o operatie poate avea unul dintre urmãtoarele douã formate:

Format Explicatie
1 a b p descrie o operatie de tip 1 (primarul va da tuturor copiilor din intervalul [a,b] câte o bilã inscriptionatã cu numãrul natural p).
2 a b k descrie o operatie de tip 2 (primarul îi întreabã pe copii care este numãrul inscriptionat pe cea de-a k-a bilã din sirul format din bilele copiilor din intervalul [a,b], stiind cã bilele sunt asezate în ordinea crescãtoare a numerelor inscriptionate pe ele).

Date de iesire
Fisierul de iesire bile.out va contine câte o linie pentru fiecare operatie de tipul 2 din fisierul de intrare. Pe cea de-a i-a linie va fi scris un numãr întreg care reprezintã rãspunsul pentru cea de-a i-a operatie de tip 2 din fisierul de intrare.

Restrictii si precizari
1 <= N <= 30000
1 <= M <= 30000
1 <= numerele inscriptionate pe bile <= 30000
Un copil poate avea mai multe bile, eventual de aceeasi valoare.
În urma unei operatii de tip 2, configuratia bilelor rãmâne neschimbatã.
Initial fiecare copil are 0 bile.

Exemplu

bile.in bile.out

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

Timp maxim de executie/test: 3 secunde
Memorie totala disponibila 32 MB, din care 1 MB pentru stiva.

Daniel Pasaila
 Universitatea "Al. I. Cuza" Iasi
Facultatea de Informatica
 Contact:danielpasaila@yahoo.com