Little Matej is solving an OOP (Object-oriented programming) laboratory exercise and he's having trouble with solving one subtask.
He is given a set that contains *
and lowercase letters of the English alphabet. For example,
*
, kul*to
, ana*
.
A pattern is said to cover a word if such an array of letters (which can be empty) exists that, when
replacing the character *
, the pattern and the word become completely identical. It is necessary to
output how many words each pattern covers.
Input
The first line of input contains two integers
Each of the following
Each of the following
The total number of characters will be less than
Output
Output
Scoring
In test cases worth 40% of total points, it will additionally hold
Sample Input 1
3 3
aaa
abc
aba
a*a
aaa*
*aaa
Sample Output 1
2
1
1
Sample Input 2
5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c
Sample Output 2
5
0
2
Comments