OOP

문제

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 N words. He is also given Q queries where each query is one pattern. A pattern consists of a single character “*” 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.

입력

The first line of input contains two integers N and Q (1 ≤ N, Q ≤ 100 000).

Each of the following N lines contains a word that consists of lowercase letters of the English alphabet.

Each of the following Q lines contains a pattern for which you need to output how many words from the first set it covers.

The total number of characters will be less than 3 000 000.

출력

Output Q lines, the k^th line containing the number of words that the k^th pattern covers.

3 3
aaa
abc
aba
a*a
aaa*
*aaa

2
1
1

5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c

5
0
2