mesaj

Se dă un şir de caractere de lungime $L$. Acest şir conţine un mesaj ascuns şi a fost obţinut prin concatenarea cuvintelor care formau mesajul şi apoi inserarea unor caractere întâmplătoare la poziţii întâmplătoare în şir. $N$ lexicografi s-au decis să descifreze mesajul. În acest scop, lexicografii vin pe rând (în ordine, de la $1$ la $N$) şi fiecare lexicograf adaugă un cuvânt la un dicţionar. Iniţial dicţionarul este vid.

După ce a adăugat cuvântul, fiecare lexicograf încearcă să descopere mesajul ascuns în şir.
În acest scop, lexicograful partiţionează şirul într-un număr maxim de subsecvenţe, astfel încât fiecare subsecvenţă să conţină ca subşir unul dintre cuvintele existente în dicţionar la momentul respectiv. Deci numărul maxim de subsecvenţe în care a fost partiţionat şirul reprezintă de fapt numărul de cuvinte din mesaj
identificate de lexicograf (cuvintele din mesaj nu sunt în mod necesar distincte).

Cerinţă

Aflaţi pentru fiecare lexicograf numărul de cuvinte din mesajul descifrat de el.

Date de intrare

Pe prima linie a fişierului de intrare mesaj.in se află şirul de caractere dat. Pe a doua linie se află numărul întreg $N$ care reprezintă numărul de lexicografi. Pe fiecare dintre următoarele $N$ linii se află câte un şir de caractere. Mai exact, pe cea de a $i$-a linie dintre cele $N$ se află cuvântul adăugat la dicţionar de lexicograful $i$.

Date de ieşire

Fişierul de ieşire mesaj.out va conţine $N$ linii. Pe linia $i$ va fi scris numărul de cuvinte ale mesajului descifrat de lexicograful $i$.

Restricţii şi precizări

• $1 \leq L \leq 1 \ 000$
• $1 \leq N \leq 5 \ 000$
• Atât cuvintele cât şi şirul dat sunt formate din caractere cu coduri ASCII de la $33$ la $127$ (deci nu conţin spaţii)
• Lungimile cuvintelor nu vor depăşi $L$
• Se face distincţie între majuscule şi minuscule (a este diferit de A)
• Suma lungimilor cuvintelor este mai mică sau egală cu $10 \ 000$
• O subsecvenţă a unui şir este formată din caractere consecutive din şirul respectiv.
• Un subşir al unui şir este format din caractere (nu neapărat consecutive) ale şirului respectiv, în ordinea în care acestea apar în şir.

Exemplul 1

mesaj.in

omuliosu
6
omul
iscusit
lis
om
ou
li

mesaj.out

1
1
1
2
2
3

Explicație

omul
omul
omul sau lis
om lis
om lis sau ou lis sau om ou sau ou ou
om li ou sau ou li ou