Zadanie

Ja som chvíľu nedával pozor…

Počet bodov: 100

Bonifác si nedá nikým povedať a dookola každému ukazuje svoj síce pôsobivý ale už neskutočne otrepaný trik.

Má vrece, do ktorého vkladá predmety, a občas z neho tieto predmety vyberá. Každá vec je popísaná jedným slovom, ktoré obsahuje iba malé písmena anglickej abecedy. Raz za čas odtiaľ vytiahne niečo čo tam ani nevkladal, napríklad zajaca alebo asistentku rozpílenú na polovicu, avšak to sa tejto úlohy netýka.

Bonifác dokončil svoje predstavenie. Rád by teraz zistil ako veľmi dával jeho jediný divák pozor. Začal sa vás pýtať otázky typu: “Koľko vecí začínajúcich na jab sa vo vreci nachádzalo v čase t?” A aj keď predstavenie trvalo niekoľko hodín, on vám dáva na všetky odpovede iba pár sekúnd. ## Vstup

Na prvom riadku vstupu je kladné celé číslo \(n\): počet operácií s vrecom. Platí \(n \leq 50\,000\).

Nasleduje \(n\) riadkov, každý popisuje jednu operáciu s vrecom. Má tvar \(+\ X\), ak do vreca bola vložená vec s menom \(X\), alebo \(-\ X\), ak Bonifác z vreca vybral vec s menom \(X\). Môžete predpokladať, že vec s menom \(X\) naozaj bola vo vreci. Do vreca samozrejme môže vložiť vec rovnakým názvom viac krát.

Následne vám Bonifác začne klásť otázky. Každá otázka má tvar \(t\ X\) tento popis zodpovedá otázke: “Koľko veci začínajúcich na \(X\) bolo vo vreci po prvých \(t\) operáciách?” \(t\) je celé číslo a platí \(0 \leq t \leq n\). \(X\) je slovo obsahujúce iba malé písmena anglickej abecedy.

Obmedzenia

Dĺžka všetkých mien vecí dokopy nepresiahne \(2\,000\,000\). (To zahŕňa operácie aj otázky.)

Výstup

Pre každú otázku vypíšte jedno celé číslo: počet veci vo vreci po \(t\) operáciách, ktorých meno sa začína na uvedený prefix.

Na otázky je nutné odpovedať online: kým nezodpoviete aktuálnu otázku, nedostanete ďalšiu. Bonifác chce odpoveď predsa hneď! Pri odpovedi nezabudnite flushnúť výstup, aby sa hneď odoslal testovaču.

Príklad

Input:

5
+ jablko
+ ja
+ jablko
- ja
- jablko
2 j
5 jabl
3 ja
1 j
0 x
3 jablk
4 ja
-1

Output:

2
1
3
1
0
2
2