C. 弦论(another version)

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

这是网络赛中同名题的另一个版本,注意,该版本不是网络赛版本的交互器,在两个版本中,查询内容不同,网络赛版本中的查询是前缀串,该版本中的查询是子串,两个版本的数据范围完全不同

kuro最近在学习巧克力物理学课程时,老师在解释弦论(String theotry)的相关内容时,提到了下面这个问题。

个字符串,仅由小写英文字母组成,总长为,每次操作会进行一次询问,询问某个字符串在所有字符串中作为子串共出现了多少次.

输入格式

每个测试点的第一行为两个数(),表示共有个字符串,总长为

接下来的行,每行有1个字符串,仅由小写英文字母组成。

接下来的一行是一个数字q,表示询问数量

接下来的行,每行有1个字符串,仅由小写英文字母组成.保证所有查询字符串长度的和不超过.

输出格式

对于每次询问,你需要输出一个整数,表示询问字符串在所有隐藏的字符串中作为子串共出现了次。

样例

输入 #1

3 9
aaa
aba
aab
2
a
aa

输出 #1

7
3

输入 #2

4 10
a
aaa
aa
aaaa
4
a
aa
aaa
aaaa

输出 #2

10
6
3
1