Ianus Timidus Ordinator sa nestal senátorom náhodou. K postaveniu mu okrem pôvodu pomohli všemožné intrigy, ale hlavne perfektné porozumenie mestu a jeho obyvateľom. Väčšinu z nich síce tvoria neušľachtilí a kultúrne zaostalí plebejci, aj tí však vedia byť, pri správnom nasmerovaní, nesmierne užitoční. Napríklad platia dane, s radosťou šíria rôzne starostlivo vymyslené klebety, a občas sa vzbúria proti oponentom, ktorých treba práve zosadiť z mramorových lavíc.

Na oplátku im stačí málo – chlieb a hry. Chlieb preto, že s plnými ústami sa ťažko sťažuje. Hry zase slúžia na ventiláciu frustrácie z vlastného života – nie je predsa nič upokojujúcejšie, ako sledovať profesionálneho gladiátora zvádzať krvavý boj na život a na smrť s divokou šelmou z ďalekej Afriky.

Každá hra sa však postupne ohrá a potrebuje nejakú zmenu. A keďže naučiť levy žrať gladiátorov novými, zaujímavejšími spôsobmi sa nedarí, Ianus sa rozhodol pri organizovaní ďalších hier trochu ozvláštniť pravidlá boja…

Boj nebude prebiehať celý naraz, ako to bývalo doteraz, ale bude sa riadiť losovaním písmen z mešca (výborne, to pridá celej akcií určitý moment prekvapenia, a možno konečne podnieti poriadny rozmach stávkovania!). Pri vytiahnutí nového písmena sa skontroluje, či je možné zo všetkých doteraz potiahnutých písmen poskladať prezývku nejakého gladiáta v aréne. Ak áno, všetci gladiátori, ktorých prezývka sa dá poskladať, idú okamžite bojovať s levmi… a ak niektorý z nich boj náhodou prežije, získa slobodu a posadí sa do hľadiska.

Extrémne dôležité je tu slovo okamžite – to najhoršie, čo sa môže stať, je, že po potiahnutí písmena budú zodpovední úradníci tak dlho premýšlať nad tým, ktorých gladiátorov poslať do boja, až to plebejcov prestane baviť, z arény nahnevane odídu, rozhádžu všade popcorn a možno vyplienia polku mesta. Je teda nutné zabezpečiť, že všetko pôjde ako po masle.

Úloha

Dostanete zoznam prezývok všetkých gladiátorov v aréne, tvorených malými písmenami abecedy (ako inak, latinskej), a malými rímskymi čislicami. Ďalej budete dostávať poradie, v ktorom sa z mešca ťahajú písmená.

Pre každé potiahnuté písmeno vypíšte počet gladiátorov vyslaných do boja po jeho potiahnutí.

Pozor, na otázky musíte (s výnimkou druhej sady) odpovedať online, teda ďalšiu otázku dostanete vždy až potom ako odpoviete na predošlú!

Formát vstupu a výstupu

V prvom riadku vstupu sú čísla $G$ a $L$ oddelené medzerou udávajúce postupne počet gladiátorov a počet písmen ťahaných z mešca. Nasleduje $G$ riadkov s prezývkami gladiátorov, ktorých dĺžka je medzi $2$ a $10^5$. Je garantované, že súčet dĺžok prezývok gladiátorov na vstupe nepresiahne $10^5$. Túto časť vstupu dostanete naraz.

Po nich postupne dostanete $L$ riadkov s písmenami, v poradí v akom sa ťahajú z mešca. Pre každý z nich vypíšte jeden riadok s počtom gladiátorov, ktorí začnú bojovať na základe jeho potiahutia. Okrem druhej sady nedostanete nové písmeno skôr, než vypíšete odpoveď.

Odporúčame zavolať funkciu flush po každom vypísanom riadku, aby program nečakal, kým sa operačný systém rozhodne vyprázdniť zásobník štandardného výstupu. V C++ môžete použiť std::cout.flush(), alebo jednoducho vypisovať nové riadky pomocou std::endl namiesto \n. V Pythone stačí pridať argument funkcií print(..., flush=True).

Existujú štyri testovacie sady, pričom vo všetkých platí, že $1 \leq G \leq 2\times 10^4$, $1 \leq L \leq 10^5$ a súčet dĺžok prezývok gladiátorov nepresiahne $10^5$. V jednotlivých sadách však platia nasledovné dodatočné obmedzenia:

• V prvej sade platí, že $G \leq 100$, $L \leq 100$ a a súčet dĺžok prezývok nepresiahne $1000$.

• V druhej sade dostanete všetky otázky naraz – nemusíte teda odpovedať online (ale môžete, testovacie prostredie si s tým poradí).

• V tretej sade sa nevyskytujú žiadne mená gladiátorov dlhšie než $50$ znakov.

Príklady

3 5
xii
xix
xxi
x
i
i
x
i

0
0
1
2
0

Po prvých dvoch ťahaniach nemáme dosť písmen na žiadny súboj. Z davu sa ozýva znudené zívanie a trocha netrpezlivého šomrania. Po treťom ťahaní už máme jedno x a dve i, takže vieme poskladať xii – a jeden gladiátor je hrdinsky zožratý. Po štvrtom ťahaní už máme dokomca dve x, takže dokážeme poskladať aj xix a xxi. To je teda akcia! Pred posledním ťahaním už nezostal žiaden gladiátor, ktorý by bavil publikum. Plebejci sa trúsia von z arény a idú si dať pizzu.

8 10
quis
stultus
hoc
excogitavit
aaaaaa
dii
mei
leo
o
q
u
s
d
i
i
m
l
e

0
0
0
0
0
1
1
0
0
2

Hic sunt leones.