Multiset

V úlohách Simple set 1 a Simple set 2 ste sa hrali s množinami, kde sa každý prvok mohol nachádzať najviac raz.

V tejto úlohe budete naopak pracovať s tzv. multiset ­— množina, v ktorej sa každý prvok môže nachádzať ľubovoľný počet krát.

Táto množina bude podporovať tri operácie:

1. Zistite, koľkokrát sa prvok nachádza v množine.
2. Vložte prvok do množiny.
3. Odstráňte jeden výskyt prvku z množiny.

Pokiaľ dostaneme požiadavku na odstraňovanie a daný prvok sa v množine nenachádza, táto operácia nemá žiaden efekt.

Podobne, ako v úlohách Simple set 1 a Simple set 2, nepoužívajte multiset zo štandardných knižníc, ale naprogramujte si vlastnú dátovú štruktúru. V tejto úlohe vám bude stačiť nevyvažovaný binárny strom (ale rovnaké prvky nedávajte každý do iného vrcholu, dostanete škaredé TLE), ale opäť vám nikto nebráni strom vyvažovať.

Úloha

Budete dostávať tri typy požiadaviek:

1. Zistite, koľkokrát sa číslo nachádza v množine.
2. Vložte číslo do množiny.
3. Odstráňte jeden výskyt čísla z množiny.

Na každú požiadavku prvého typu treba vypísať jedno číslo ­— koľkokrát sa dané číslo nachádza v množine.

Vstup

Na prvom riadku je číslo $n$ ($1 \leq n \leq 10^5$) ­— počet požiadaviek.

Na ďalších $n$ riadkoch sú popisy jednotlivých požiadaviek. Na $i$-tom riadku sú dve čísla $t_i$ a $x_i$ popisujúce $i$-tu požiadavku.

Ak $t_i = 1$, tak sa jedná o požiadavku prvého typu. Na túto požiadavku treba odpovedať vypísaním jedného čísla: počet výskytov $x_i$ v množine.

Ak $t_i = 2$, tak sa jedná o požiadavku druhého typu a číslo $x_i$ treba vložiť do množiny.

Ak $t_i = 3$, tak sa jedná o požiadavku tretieho typu a z množiny treba zmazať jeden výskyt čísla $x_i$.

Platí $t_i \in {1, 2, 3}$ a $1 \leq x_i \leq 10^9$.

Výstup

Pre každú požiadavku prvého typu vypíšte jeden riadok a na ňom jedno číslo ­— počet výskytov daného čísla v množine.

Príklad

9
1 4
2 2
1 2
2 2
1 2
3 2
1 2
2 4
1 4

0
1
2
1
1

Najprv sme číslo $2$ vložili do množiny dvakrát, potom sme jeden výskyt zmazali.