seti

Se pare cǎ în sfârşit cǎutǎtorii vieţii extraterestre au descoperit ceva! În cursul proiectului SETI@home a fost izolatǎ o secvenţǎ care ar putea reprezenta un semnal de la alte forme de viaţǎ inteligentǎ. Ca urmare, proiectul SETI@ONI îşi propune sǎ verifice dacǎ acel semnal provine într-adevǎr de la extratereştri sau doar de la nişte puşti care beau Fanta.

Cerinţă

Pentru comoditate, porţiunea de semnal ce trebuie analizatǎ vi se pune la dispoziţie sub forma unei succesiuni de litere ale alfabetului latin. Vi se mai pune la dispoziţie şi un dicţionar de cuvinte extraterestre, codificate în acelaşi mod. Scopul dumneavoastrǎ este sǎ numǎraţi de câte ori apare fiecare dintre aceste cuvinte în posibilul mesaj extraterestru. Pornind de la aceste date, lingviştii pot sǎ înceapǎ lucrul la traducerea mesajului.

Date de intrare

Pe prima linie a fişierului de intrare seti.in este scris numǎrul $N$ de linii ale mesajului. Urmeazǎ $N$ linii, fiecare conţinând exact $64$ de litere ale alfabetului latin urmate de marcajul de sfârşit de linie. Prin alipirea acestor bucǎţi se obţine mesajul de analizat, format din $64 \times N$ litere. Pe următoarea linie este scris numǎrul $M$ de cuvinte din dicţionar. Urmeazǎ apoi $M$ linii, fiecare conţinând un cuvânt din dicţionar, reprezentat ca o secvenţă de cel puţin una şi cel mult $16$ litere. Cuvintele nu sunt neapǎrat distincte.

Date de ieşire

Fişierul de ieşire seti.out va conţine exact $M$ linii. Pe linia cu numǎrul $i$ va fi scris numǎrul de apariţii în mesajul extraterestru ale cuvântului cu numǎrul $i$ din dicţionar. Numǎrul de apariţii nu va depǎşi niciodatǎ $65535$. Orice apariţie a unui cuvânt trebuie numǎratǎ, chiar dacǎ se suprapune peste alte apariţii. Se va face diferenţǎ între litere mari şi litere mici.

Restricţii

• $0 ≤ N < 2 \ 048$;
• $0 ≤ M ≤ 32 \ 000$.

Exemplu

seti.in

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaBaba
babaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaBaB
3
b
bab
b

seti.out

3
2
3