给定一个数组 $$$s$$$,由 $$$n$$$ 不同的字符串组成。每个字符串由 $$$m$$$ 小写拉丁字母组成。
您必须回复 $$$q$$$ 查询。每个查询包含一个长度为$$$m+1$$$的字符串$$$t$$$。计算索引$$$i$$$的个数,使得如果允许在任意位置插入一个字母,则可以从字符串$$$s_i$$$中得到字符串$$$t$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le m \le 10$$$) — 数组中字符串的数量和每个字符串的长度。
以下 $$$n$$$ 行包含字符串 $$$s_i$$$。所有给定的字符串都不同。
下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) - 查询数。
以下 $$$q$$$ 行包含长度为 $$$m + 1$$$ 的查询字符串 $$$t$$$。
输出
对于每个查询,打印索引 $$$i$$$ 的数量,这样,如果允许在任意位置插入一个字母,则可以从字符串 $$$s_i$$$ 中获取查询中的字符串。
示例
输入 #1
2 1 a c 4 aa ca mm cf
输出 #1
1 2 0 1
输入 #2
6 3 dba abd cbb ada add bdd 5 ccbb abdd adba bada dddd
输出 #2
1 3 2 1 0
注意
示例第一个测试的说明:
- 字符串a可以通过插入一个字母转化为aa;
- 字符串a和c都可以通过插入一个字母转换为ca;
- a和c都不能通过插入一个字母来转换为mm;
- c 通过插入一个字母可以转换为 cf。