3. Otravné notifikácie

Baklažán má konečne nový mobil. A nie hocijaký. Je to novučičký KSP Nokia Lumia S6, limitovaná edícia, s umelou inteligenciou na každom pixeli. Konečne totiž pochopil, že tie smartfóny sú v skutočnosti celkom užitočné, keď mu na starom mobile došla pamäť pri vkladaní nového kontaktu.

Jeho nový mobil sa mu ale bohužiaľ snaží dokázať opak: vyhadzuje jednu notifikáciu za druhou, s náhodnou informačnou hodnotou. Nemôže ich všetky ignorovať, lebo čo ak tá nasledujúca bude dôležitá? Už mu dochádza trpezlivosť… Koľko notifikácii ešte bude musieť dnes prečítať?

Úloha

Na začiatku nie sú na mobile žiadne neprečítané notifikácie. Následne prichádzajú tri typy udalostí:

1. Aplikácia \(x\) vygenerovala jednu novú (neprečítanú) notifikáciu.
2. Baklažán prečítal všetky (neprečítané) notifikácie od aplikácie \(x\).
3. Baklažán prečítal prvých \(t\) neprečítaných notifikácii. Môžete predpokladať, že Baklažán má aspoň toľko neprečítaných notifikácii, ale môže ich mať aj viac.

Po každej udalosti vypíšte, koľko notifikácii je ešte neprečítaných. (Do toho sa nerátajú notifikácie, ktoré ešte neboli vygenerované.)

Formát vstupu

Na prvom riadku vstupu sú dve čísla oddelené medzerou: počet aplikácii \(n\) a počet udalostí \(q\). Platí \(1 \leq n, q \leq 500\,000\).

Každý z nasledujúcich \(q\) riadkov popisuje jednu udalosť. Popis udalosti má nasledovný formát: 1 <x>, 2 <x> a 3 <t> postupne pre udalosti prvého, druhého a tretieho typu. Platí \(1 \leq x \leq n\) (aplikácie číslujeme od \(1\)) a \(1 \leq t\).

Formát výstupu

Vypíšte \(q\) riadkov, na \(i\)-tom z nich nech je počet zostávajúcich notifikácii po \(i\)-tej udalosti.

Hodnotenie

Sú \(4\) testovacie sady, každá za \(2\) body. Platia v nich nasledovné obmedzenia:

Príklad

Input:

3 4
1 3
1 1
1 2
2 3

Output:

1
2
3
2

Input:

2 4
1 1
1 2
3 1
2 1

Output:

1
2
1
1

Pri tretej udalosti Baklažán prečíta notifikáciu aplikácie \(1\), nakoľko tá je prvá v poradí. Pri štvrtej udalosti nič neprečíta, lebo aplikácia \(1\) už nemá žiadne ďalšie notifikácie.

Input:

4 7
1 2
1 4
1 2
2 3
1 3
3 1
3 1

Output:

1
2
3
3
4
3
2

Pri štvrtej udalosti Baklažán nič neprečíta, lebo sa pozerá na aplikáciu \(3\), ktorá vtedy ešte nič nevygenerovala.