题目描述

给定 $N$ 个单词和 $Q$ 个模板，一个模板由一个 * 和一些小写字母组成。一个模板覆盖了一个单词当且仅当将 * 替换为任意字母后，模板和单词能够完全重合。对于每个模板，求出它能够覆盖多少个单词。

输入格式

输入第一行两个整数 $N,Q$。

接下来的 $N$ 行，每行一个小写字母组成的单词。

接下来的 $Q$ 行，每行一个模板。

以上读入的字符总数少于 $3\times 10^6$。

输出格式

输出共 $Q$ 行。表示每个模板能够覆盖的单词的个数。

输入输出样例 #1

输入 #1

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

输出 #1

2
1
1

输入输出样例 #2

输入 #2

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

输出 #2

5
0
2

说明/提示

数据规模与约定

对于 $40\%$ 的数据，$1\le N,Q\le 10^3$；
对于 $100\%$ 的数据，$1\le N,Q\le 10^5$。