Državno natjecanje iz informatike 2018. / Prva podskupina (1. i 2. razred) - 3. zadatak

Čekajući rezultate natjecanja, Aron se odlučio zabaviti igrajući igru SuPeRtEtRiS na svom nosiglasu\(1\). SuPeRtEtRiS je najnovija hit igra koja crpi inspiraciju iz najstarije hit igre Tetris. U SuPeRtEtRiSu razne figure (koje su drugačijeg oblika nego u Tetrisu) redom padaju s vrha ekrana. Svaka figura u SuPeRtEtRiSu sastoji se od stupaca određenih duljina tako da je gornja stranica figure ravna, tj. možemo reći da stupci različitih duljina “vise” s gornjeg ruba figure. Jedna takva figura prikazana je crnom bojom na donjoj slici.

Kada se figura pojavi na vrhu ekrana, igrač je može najprije pomicati lijevo i desno, a potom spustiti dok figura ne padne na dno ekrana ili na neku od već spuštenih figura. Nakon spuštanja figure uklanjaju se potpuno popunjeni redovi ekrana ispod kojih ne postoji nijedno prazno polje. Za razliku od Tetrisa, igrač figuru ne može rotirati.

Uz Arona, SuPeRtEtRiS igra i Krešo koji ga je odavno svladao. Krešo je primijetio da Aronu baš i ne ide te mu je ponudio pomoć tako što je izmislio vježbu kojom će ga trenirati. On će Aronu zadati izgled ekrana kao niz visina stupaca koji opisuju strukturu već spuštenih figura (koje neće tvoriti “rupe”) te će ga za različite nove figure pitati koliko se najviše redova može ukloniti s ekrana u slučaju da je ta figura iduća na redu. Upiti su međusobno neovisni, tj. nove figure ne ostaju na ekranu za iduće upite. Pomozite Aronu tako što ćete riješiti vježbu koju mu je zadao Krešo. Na slici je prikazan početni izgled ekrana te prva figura iz drugog primjera na poziciji na kojoj može ukloniti dva reda, što je ujedno i najviše što se može ukloniti tom figurom.

Ulazni​ podaci

U prvom retku nalazi se broj \(N ( 1 \leq N \leq 1 000 000 )\), broj parova brojeva koji opisuju početni izgled ekrana s lijeva na desno. U svakom od sljedećih \(N\) redaka nalaze se dva broja \(L\) i \(H ( 1 \leq L \leq 1 000 000, 0 \leq H \leq 1 000 000 )\) koji označavaju da je u postojećoj strukturi idućih \(L\) stupaca visine \(H\) polja. Barem jedan zadani stupac bit će visine \(0\) i zadani stupci pokrivat će cijelu širinu ekrana.

U sljedećem retku nalazi se broj \(M ( 1 \leq M \leq 100 000 )\), broj figura. Slijedi \(M\) blokova koji opisuju figure. Za svaku figuru se u prvom retku bloka nalazi prirodan broj \(K ( 1 \leq K \leq 1 000 000 )\), broj parova brojeva koji opisuju figuru s lijeva na desno. U svakom od idućih \(K\) redaka nalaze se dva broja \(L ( 1 \leq L \leq 100 000 000 )\) i \(H ( 1 \leq H \leq 1 000 000 )\) koji označavaju da je u figuri idućih \(L\) “visećih” stupaca visine H. Ukupan broj stupaca figure bit će manji ili jednak broju stupaca ekrana. Zbroj brojeva \(K\) za sve figure bit će najviše \(1 000 000\).

Izlazni podaci

Za svaku od \(M\) figura u zaseban redak ispišite traženi broj redova koji se može ukloniti nakon njezinog spuštanja.

Bodovanje

U test podatcima vrijednim \(20 \%\) bodova vrijedi \(M \leq 100\) te ekran sadrži najviše \(100\) stupaca.

U test podatcima vrijednim dodatnih \(20 \%\) bodova vrijedi \(M \leq 5000\) te je broj stupaca na ekranu najviše \(5000\).

U test podatcima vrijednim dodatnih \(40 \%\) bodova, broj stupaca na ekranu nije veći od \(1 000 000\).

U posljednjih \(20 \%\) test podataka nema dodatnih ograničenja.

Primjeri test​ podataka

Ulaz

3
1 3
1 0
1 3
3
1
1 3
2
1 4
1 1
2
1 2
1 1

Izlaz

3
3
0

Ulaz

7
2 5
1 2
1 0
1 2
3 1
1 3
1 2
2
1
1 3
4
1 1
1 4
1 2
3 3

Izlaz

1
2