DRŽAVNO NATJECANJE 2013. – Prvi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Mirku i Slavku su dosadile postojeće igračke, pa su odlučili sami konstruirati jednu novu.

Skupili su nešto starih dasaka, čavala, epruveta i paket franja (staklenih kuglica u nekim krajevima Hrvatske poznatih kao “pikule” ili “špekule”), kojeg je Mirko dobio za neki od proteklih Božića.

Igračku koju su sagradili možemo predstaviti kao rešetku širine 1 i dužine N.

Za svaku su ćeliju u rešetki zatim pričvrstili epruvetu u koju stane točno M franja.

Željeli su se brzo početi igrati pa su iz nehaja razbili K epruveta.

Igra počinje! Mirko je igračku lagano nagnuo udesno, a zatim je Q puta zagrabio određenu količinu franja te ih pokušao ubaciti u neku od epruveta.

Naravno, moguće je da neke franje neće stati u epruvetu u koju ih Mirko pokušava ubaciti pa će se višak “preliti” udesno.

Franje će tada završiti u prvoj epruveti udesno u kojoj ima slobodnog mjesta ili će pasti kroz prvu rupu ispod koje nije epruveta.

Franje se također mogu preliti preko krajnjeg desnog ruba igračke i pasti na tlo.

Napišite program koji će na temelju opisa rešetke nakon svakog Mirkovog ubacivanja izračunati broj epruveta u kojima se nakon dosadašnjih ubacivanja nalazi barem jedna franja te ukupan broj franja koje su od početka igre nakon dosadašnjih ubacivanja (uključujući i trenutno) pale na tlo.

Ulazni podaci

U prvom retku ulaza nalaze se prirodni brojevi N i M, (1 ≤ N ≤ 1 000 000 000, 1 ≤ M ≤ 1 000) duljina rešetke i kapacitet svake epruvete.

U drugom retku ulaza nalaze se prirodni broj K, broj razbijenih epruveta (1 ≤ K ≤ N, 1 ≤ K ≤ 100 000) i zatim K prirodnih brojeva Ei (1 ≤ Ei ≤ N), redni brojevi razbijenih epruveta.

Epruvete su označene brojevima od 1 do N s lijeva na desno. Brojevi Ei bit će poredani uzlazno.

U trećem redu ulaznih podataka nalazi se prirodni broj Q, broj Mirkovih ubacivanja franja u epruvete (1 ≤ Q ≤ 100 000).

U svakom od sljedećih Q redova nalaze se po 2 prirodna broja, Xi i Si (1 ≤ Xi ≤ N, 1 ≤ Si ≤ 100 000), redni broj epruvete i količina franja koju Mirko pokušava ubaciti u i-tom ubacivanju.

Izlazni podaci

Potrebno je ispisati Q redaka, gdje se u i-tom retku izlaza nalaze dva broja odvojena razmakom:

broj epruveta koje nakon i-tog ubacivanja sadrže barem jednu franju te broj franja koje su od početka igre do tog ubacivanja (uključujući i to ubacivanje) pale na tlo.

Napomena: Rješenje ne mora nužno stati u 32-bitni cjelobrojni tip podataka.

Primjeri test podataka

Ulaz

10 2
3 3 8 9
3
1 5
3 7
4 3

Izlaz

2 1
2 8
4 8

Objašnjeje

Pojašnjenje prvog test primjera: Primjer je prikazan na slikama.

U prvom ubacivanju Mirko je zagrabio pet franja te time popunio prvu i drugu epruvetu, dok je peta franja kroz rupu pala na tlo.

U drugom ubacivanju Mirko je sve franje ubacio u rupu na mjestu gdje je trebala biti treća epruveta.

U trećem ubacivanju popunjena je četvrta epruveta te je jedna franja završila u

petoj epruveti.

Ulaz

12 3
4 1 4 7 11
4
3 2
2 5
2 1
8 8

Izlaz

1 0
2 1
2 2
5 2