8. Akútna výstavba

Koho by už len zaujímala diaľnica, aj tak všetci vieme, že to hlavné, čo sa v okolí Kokavy nad Rimavicou bude stavať je predsa masivácky mrakodrap. Poďme sa teda za ľubozvučných zvukov výstavby pozrieť na aktuálnu situáciu na stavenisku.

Asi si viete presne predstaviť, ako to na takej stavbe vyzerá. Väčšina robotníkov len tak postáva okolo a len zopár vyvolených pracuje. A aby to nebolo málo, tak ešte chodia aj na pravidelné prestávky. Stavbyvedúceho Dušana už samozrejme nebaví toto všetko sledovať. To ale nemení nič na tom, že stále potrebuje svojich nadriadených informovať o postupe stavby. Na to ale potrebuje vždy vedieť, koľko chlapov aktuálne pracuje.

Presne preto povolal vás, lacnopracujúcich brigádnikov, aby ste mu tieto dáta pomohli získať a on si naďalej mohol v kľude užívať túto malebnú scenériu.

Úloha

Na vstupe dostanete popis jednotlivých Dušanových robotníkov. Kým je \(i\)-ty robotník prítomný na stavenisku, najprv prvých \(a_i\) hodín obdivuje prácu ostatných, a následne ďalších \(b_i\) hodín maká. Potom zase \(a_i\) hodín obdivuje a \(b_i\) hodín maká, a takto sa to pravidelne strieda, kým zas neodíde zo staveniska preč dať si pauzu.

Každú hodinu nastane jedna z dvoch situácií. Buď nejaký robotník príde z pauzy na stavenisko (a začne hneď svoj pracovný cyklus tým, že bude obdivovať ostatných) alebo sa naopak jeden robotník na stavenisku rozhodne, že už toho má dosť, a ide pauzovať.

Dušana by po každej takejto zmene zaujímalo, koľko robotníkov počas nasledujúcej hodiny na výstavbe aktívne pracuje.

Na začiatku sú všetci robotníci na pauze.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú čísla \(n\) a \(m\) (\(1 \le n,m \le 2 \cdot 10^5\))¹, reprezentujúce počet robotníkov a počet hodín, ktoré prebieha stavba.

Nasleduje \(n\) riadkov, na každom z nich sú dve čísla \(a_i\) a \(b_i\) (\(1 \le a_i, b_i \le 2 \cdot 10^5\)), ktoré popisujú pracovný cyklus \(i\)-teho robotníka. Tento robotník najprv \(a_i\) hodín obdivuje prácu ostatných a potom \(b_i\) hodín aktívne pracuje. Toto sa opakuje, až kým znova nepôjde pauzovať.

Na ďalších \(m\) riadkoch sa nachádzajú dve čísla \(op\) a \(k\) (\(0 \le k < n\)), ktoré hovoria o tom, čo sa v danú hodinu stalo. Ak \(op = 1\), tak sa robotník číslo \(k\) vrátil z pauzy. Ak \(op = -1\), tak naopak robotník číslo \(k\) práve odchádza na pauzu. Ak má nejaký robotník prísť z pauzy, tak doteraz určite bol na pauze a ak má naopak odísť na pauzu, tak doteraz určite bol na stavenisku. Robotníkov číslujeme od \(0\).

V jednotlivých sadách navyše platia nasledujúce obmedzenia:

Formát výstupu

Pre každú hodinu (teda tesne po tom, čo nejaký robotník odíde alebo príde) vypíšte na samostatný riadok jedno číslo, počet robotníkov, ktorí v túto hodinu aktívne pracujú.

Upozornenie

Odporúčame použiť rýchle načítavanie vstupu v jazyku C++. Teda namiesto std::endl použiť \n a vypnúť sychronizáciu s C-čkovým IO pomocou cin.tie(0)->sync_with_stdio(0).

Príklad

Input:

3 6
1 1
6 3
2 1
1 0
-1 0
1 0
1 2
1 1
-1 1

Output:

0
0
0
1
0
2

• Prvá hodina začne príchodom robotníka 0, ktorý ju strávi obdivovaním rozostavaného mrakodrapu a osamelou meditáciou o význame stavby pre rozvoj a blahobyt dediny.
• V druhej hodine bude po jeho odchode stavenisko opustené, teda aj teraz bude aktívne pracovať 0 robotníkov.
• V tretej hodine sa vráti, ale aj keď už predtým hodinu obdivoval, začne zase od začiatku obdivovaním.
• Vo štvrtej hodine konečne prvýkrát začne robotník 0 aktívne pracovať a robotník 2 obdivuje, ako mu to ide.
• V piatej hodine ale znova prestane a robotníci 1 a 2 tiež len obdivujú, čo všetko už stihol postaviť.
• Nakoniec v šiestej hodine budú aktívne pracovať robotníci 0 aj 2. Aký úspešný deň!