C. 寻迹

无论是古代还是近代，凭人类一己之力，要想穷尽世界上的知识来寻找某一特定答案，可以说是不可能做到的事情。而信息技术的发展则让现代人拥有了空前的信息检索、信息聚合、信息分析能力。表达式匹配是信息检索技术的一个重要组分，现在我们来研究一个表达式匹配问题。

现有 个字符串 ，全部由小写字母组成，另有 个字符串 ，除小写字母外，每个字符串中有且仅有一个 字符，其中 前的字符串匹配 的一个前缀， 后的字符串匹配 的一个后缀， 可以匹配任何字符串（含空串）。对每个字符串 ，求有多少个字符串 能被匹配。

第一行包含两个正整数 和 。

接下来 行，每行一个字符串表示一个文件名。

接下来 行，每行一个字符串表示一次询问。

对每次询问输出一行一个整数表示答案。

样例输入 1

6 5
a
ab
ac
abc
abdc
bc
a*c
*c
ab*
a*dc
*d

见附加文件中的 regex1.in

样例输出 1

3
4
3
1
0

见附加文件中的 regex1.out

样例输入 2

14 7
frnoiag
frapiocu
frwccu
frnoicu
frctsccu
ysjnoiag
ysjwccu
ysjnoipak
ysjnoicu
ysjapiocu
sjbnoiag
sjbapiocu
sjbwccu
sjbnoipak
fr*
*noiag
sjb*
fr*cu
*noipak
ysj*
frnoi*

见附加文件中的 regex2.in

样例输出 2

5
3
4
4
2
5
2

见附加文件中的 regex2.out

样例 3 ~ 4

符合测试点 的全部性质，见附加文件中的 regex3~4.in/out

样例 5

与测试点 规模相同，但不具有特殊性质，见附加文件中的 regex5.in/out

对于 的数据：，。

本题考察 Trie、 树状数组和 DFS 序。