Se consideră alfabetul compus din literele mici, de la a la z, fără diacritice. Se numeşte cuvânt un şir finit, eventual vid, de litere din alfabet. Se numeşte mască un şir de caractere din alfabet având eventual în plus caracterele ? şi * cu următoarea semnificaţie: caracterul ? înlocuieşte oricare din literele de la a la z (o singură literă) iar caracterul * înlocuieşte un cuvânt oarecare, eventual vid, format cu litere de la a la z.

Spre exemplu avem masca a?b*c. Dacă avem 3 cuvinte şi anume abbc, acbaac şi abac atunci primele 2 se potrivesc cu masca.

Cerința

Considerându-se o listă de cuvinte, să se determine:

a) Numărul de cuvinte distincte.
b) Numărul de cuvinte distincte ce se potrivesc cu o mască dată, adică se pot obţine prin înlocuirea caracterelor ? şi * din mască.

Date de intrare

Fișierul de intrare masca.in conține:

• Pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
• Pe a doua linie o mască E (şir de caractere).
• Pe a treia linie numărul N de cuvinte.
• Pe fiecare din următoarele N linii câte un cuvânt S (şir de caractere) cu litere din alfabet.

Date de ieșire

Fișierul de ieșire masca.out va conține:

• Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerinţă. În acest caz, în fişierul de ieşire se va scrie un singur număr natural N1, reprezentând numărul de cuvinte distincte S din fişierul de intrare.
• Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerinţă. În acest caz, în fişierul de ieșire se va scrie un număr natural N2, reprezentând numărul de cuvinte distincte S ce se potrivesc cu masca E.

Restricții și precizări

• Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.
• 1≤N≤1000
• Lungimea unui cuvânt oarecare S cât şi a expresiei mască E este între 1 şi 100 de caractere.
• În expresia mască E sunt cel mult două caractere *.

Exemplul 1

masca.in

1
a*a?b
7
ababb
aab
aabb
aab
abcaab
abcaab
ababa

masca.out

5

Explicație

Cuvintele aab si abcaab apar de cate 2 ori. Atenţie! Pentru acest test se rezolvă doar cerinţa a).

Exemplul 2

masca.in

2
a*a?b
7
ababb
aab
aabb
aab
abcaab
abcaab
ababa

masca.out

3

Explicație

Cuvintele ababb, aabb și abcaab se potrivesc cu masca. Cuvântul abcaab apare de 2 ori. Atenţie! Pentru acest test se rezolvă doar cerinţa b).