4. Zabudnuté algoritmy

Hodobox je už vysokoškolák, a preto bol tento rok prvýkrát na školskom kole súťaže ACM. A čo sa stalo-nestalo, predbehla ho stredoškoláčka a ešte aj chlapec so zápalom pľúc! Teraz sa Hodobox snaží prejsť si všetky úlohy odznova a skúsiť si ich preriešiť. Má však malý problém. Niečo sa stalo a zabudol všetky algoritmy. Nevie už nakódiť ani len binárne vyhľadávanie, ktoré sa naučil na letnej škole.

Rozhodol sa teda, že sa všetky potrebné algoritmy znova naučí. Každá úloha sa dá definovať ako množina algoritmov, ktoré sú potrebné na jej vyriešenie. Pre jednoduchosť si algoritmy očíslujeme od \(1\) po \(1\,000\,000\) (napríklad \(47\) je binárne vyhľadávanie).

Nie je to však až také jednoduché. Rôzne úlohy vyžadujú znalosť rôznych algoritmov do rôznej hĺbky. Napríklad taký merge-sort – v jednej úlohe ním len usporiadame prvky, v inej však spočítame počet inverzií. Úloha má teda ku každému algoritmu, ktorý je potrebný na jej vyriešenie priradenú ešte aj potrebnú úroveň znalosti tohto algoritmu.

Hodobox má so sebou Paulínkinu príručku ‘How to win IOI for dummies’. V nej si Paulínka spísala všetky algoritmy od výmyslu sveta. Hodobox sa nimi teraz prehrýza a veľmi by ho zaujímalo, kedy už bude konečne schopný naprogramovať všetky úlohy zo školského kola ACM.

Úloha

Na vstupe dostanete popis školského kola, ktoré sa skladá z \(n\) úloh. Pre každú úlohu dostanete zoznam algoritmov potrebných na jej vyriešenie (číslo algoritmu a úroveň potrebnú na vyriešenie tejto úlohy).

Potom nasleduje \(p\) Hodoboxových akcií, kde si vždy zlepší chápanie nejakého algoritmu o istú úroveň. Na začiatku Hodobox nevie nič (jeho úroveň znalosti každého algoritmu je \(0\)).

Vašou úlohou je po každej akcii vypísať, koľko úloh zo školského kola je už Hodobox schopný vyriešiť.

Formát vstupu

Na prvom riadku vstupu je počet úloh \(n ~ (1 \leq n \leq 10^6)\).

Nasleduje \(n\) popisov úloh. Popis \(i\)-tej úlohy začína číslom \(a_i\) na samostatnom riadku – počet algoritmov nutných na vyriešenie \(i\)-tej úlohy (\(0 \leq a_i < 10^6\)). Potom nasleduje \(a_i\) riadkov s popismi jednotlivých algoritmov potrebných pre túto úlohu. Každý z nich obsahuje dve čísla \(x ~ (1 \leq x \leq 10^6)\) – číslo daného algoritmu a \(y ~ (1 \leq y \leq 10^9)\) – potrebná úroveň znalosti tohto algoritmu.

Zároveň platí, že \(\sum a_i \leq 10^6\).

Potom nasleduje jeden riadok s číslom \(p\) – počet akcií, kedy sa Hodobox učí nejaký algoritmus. Platí, že \(p \leq 10^6\). Nasleduje \(p\) riadkov. V každom sú dve čísla \(c_j\) a \(u_j\), kde \(c_j\) je číslo algoritmu a \(u_j\) znamená, o koľko sa Hodoboxovi zlepšila úroveň znalosti algoritmu \(c_j\). Platí že \(1 \leq c_j \leq 10^6\) a \(1 \leq u_j \leq 10^9\).

Vstupy v tejto úlohe budú veľmi veľké. V C++ preto odporúčame použiť miesto knižnice <iostream> knižnicu <cstdio>. Ak chcete použvívať <iostream>, vložte si na začiatok programu nasledovné príkazy, ktoré urýchlia vstup a výstup: ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); Na vypisovanie nového riadku tiež nepoužívajte endl, ale znak nového riadku '\n'.

V pomalších jazykoch sa nemusí dať získať plný počet bodov na testovacích vstupoch. Za optimálne riešenie však stále viete získať plný počet za popis riešenia.

Formát výstupu

Na výstupe bude \(p\) riadkov. Na \(j\)-tom riadku bude jedno číslo – počet úloh ktoré vie Hodobox vyriešiť, keď sa už zlepšil v algoritmoch \(c_1\) až \(c_j\) o príslušné úrovne.

Príklad

Input:

3
1
14 1
0
2
13 3
14 1
2
13 3
14 1

Output:

1
3

Už na začiatku vie Hodobox vyriešiť druhú úlohu, pretože na ňu netreba vedieť nič. Po prvej akcii si zlepší chápanie algoritmu 13 z 0 na 3, čo mu nepomôže k ďalšej úlohe, takže výstup je 1. Druhou akciou si zlepší chápanie algoritmu 14 z 0 na 1, čo mu pomôže vyriešiť prvú aj tretiu úlohu.

Input:

3
2
47 5
42 3
3
42 13
13 4
7 6
1
47 2
5
47 1
47 3
42 12
13 5
47 12

Output:

0
1
1
1
2

Hodobox nevie pred prvou akciou vyriešiť ani jednu úlohu. Po prvej akcii sa binárne vyhľadávanie (algoritmus 47) naučí na úroveň 1. To mu ale nepomôže k žiadnej úlohe, takže výstup je 0.

Ďalšou akciou si zlepší znalosť vyhľadávania na 4. Preto vie vyriešiť tretiu úlohu, ale nič viac. Potom sa naučí algoritmus 42 na úroveň 12, čo mu stále nepomôže k ďalším úlohám. Potom si zlepší algoritmus 13 z nuly na 5, takisto mu to nepomôže. Na prvú úlohu ma slabú znalosť algoritmu. č. 47 a na druhú zas algoritmu 7.

Poslednou akciou sa naučí algoritmus 47 na úroveň 16 (\(4 + 12\)), takže už bude vedieť vyriešiť prvú úlohu.