Description

Given $N$ words and $Q$ patterns, each pattern consists of one * and some lowercase letters. A pattern matches a word if and only if, after replacing * with some string (which can be empty), the pattern and the word can coincide exactly. For each pattern, find how many words it can match.

Input Format

The first line contains two integers $N, Q$.

The next $N$ lines each contain a word consisting of lowercase letters.

The next $Q$ lines each contain a pattern.

The total number of characters read is less than $3\times 10^6$.

Output Format

Output $Q$ lines. Each line contains the number of words that the corresponding pattern can match.

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

Hint

Constraints

For $40\%$ of the testdata, $1\le N, Q\le 10^3$.
For $100\%$ of the testdata, $1\le N, Q\le 10^5$.

Notes

This problem is translated from COCI2015-2016 CONTEST #5 T5 OOP。

Translated by ChatGPT 5