Fişierul intrare/ieşire:bile4.in, bile4.outSursă.campion 2007-2008, Runda 11, Grupa mare
AutorDaniel PasailaAdăugată dedanielpDaniel Pasaila danielp
Timp execuţie pe test1.05 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bile4

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.

Date de intrare

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:

FormatExplicatie
1 a b pdescrie 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 kdescrie 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)

Date de ieşire

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

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

Exemplu

bile4.inbile4.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?