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