你知道 Just Odd Inventions Co., Ltd. 吗？这家公司的业务是做“纯粹古怪的发明”。在这里，我们将简写其名称，称之为 JOI 公司。
最近，JOI 公司仅靠做古怪发明，盈利能力严重下滑。公司计划开展一项新业务，计划销售含有 RNA 链的液体。RNA 链被视为由 ‘A’、‘G’、‘C’、‘U’ 这 4 个字符组成的字符串。为了开展业务，JOI 公司准备了 $N$ 条 RNA 链。
JOI 公司将接受客户的 RNA 链订单，形式如下：
- 客户选择两个字符串 $P, Q$。然后，在 JOI 公司准备的 RNA 链中，销售那些前 $|P|$ 个字符为 $P$ 且后 $|Q|$ 个字符为 $Q$ 的字符串。这里，$|P|, |Q|$ 分别是 $P$ 和 $Q$ 的长度。
JOI 公司准备的 RNA 链中有多少条符合客户的订单条件？
任务
给定 JOI 公司准备的 RNA 链信息和客户的订单，编写一个程序，计算 JOI 公司准备的 RNA 链中有多少条符合客户的订单条件。
输入格式
从标准输入读取以下数据。
- 第一行包含两个空格分隔的整数 $N, M$。这意味着 JOI 公司准备了 $N$ 条 RNA 链，且有 $M$ 个客户订单。
- 接下来的 $N$ 行中的第 $i$ 行 ($1 \le i \le N$) 包含一个字符串 $S_i$，即 JOI 公司准备的第 $i$ 条 RNA 链。
- 接下来的 $M$ 行中的第 $j$ 行 ($1 \le j \le M$) 包含两个空格分隔的字符串 $P_j, Q_j$。这意味着在第 $j$ 个订单中，客户选择了两个字符串 $P_j, Q_j$。
输出格式
输出包含 $M$ 行。第 $j$ 行 ($1 \le j \le M$) 包含一个整数，表示符合第 $j$ 个订单条件的 RNA 链数量。
数据范围
所有输入数据满足以下条件：
- $1 \le N \le 100\,000$
- $1 \le M \le 100\,000$
- 每个字符串由字符 A, G, C, U 组成。
- $1 \le |S_i| \le 100\,000$ ($1 \le i \le N$)
- $1 \le |P_j| \le 100\,000$ ($1 \le j \le M$)
- $1 \le |Q_j| \le 100\,000$ ($1 \le j \le M$)
- $|S_1| + |S_2| + \dots + |S_N| \le 2\,000\,000$
- $|P_1| + |P_2| + \dots + |P_M| \le 2\,000\,000$
- $|Q_1| + |Q_2| + \dots + |Q_M| \le 2\,000\,000$
子任务
子任务 1 [10 分]
满足以下条件： $N \le 100$ $M \le 100$ $|S_i| \le 100$ ($1 \le i \le N$) $|P_j| \le 100$ ($1 \le j \le M$) * $|Q_j| \le 100$ ($1 \le j \le M$)
子任务 2 [25 分]
满足以下条件： $N \le 5\,000$ $M \le 5\,000$
子任务 3 [25 分]
满足以下条件： $|S_1| + |S_2| + \dots + |S_N| \le 100\,000$ $|P_1| + |P_2| + \dots + |P_M| \le 100\,000$ * $|Q_1| + |Q_2| + \dots + |Q_M| \le 100\,000$
子任务 4 [40 分]
无附加限制。
样例
样例输入 1
2 3 AUGC AGC G C AU C A C
样例输出 1
0 1 2
说明
在此样例输入中，JOI 公司准备了两条 RNA 链 AUGC, AGC。
- 对于第一个订单，输出 0，因为没有 RNA 链的首字符为 G 且末字符为 C。
- 对于第二个订单，输出 1，因为只有一条 RNA 链 AUGC 的前缀为 AU 且后缀为 C。
- 对于第三个订单，输出 2，因为有两条 RNA 链 AUGC, AGC 的首字符为 A 且末字符为 C。
样例输入 2
3 3 AA AA AGA AA AA AG GA AG GA
样例输出 2
2 1 1
说明
注意，相同的 RNA 链和/或相同的订单可能会出现多次。此外，订单中选择的前缀字符和后缀字符可能会重叠。例如，RNA 链 AGA 被视为前缀为 AG 且后缀为 GA 的字符串。
样例输入 3
8 7 GCGCUACCCCAACACAAGGCAAGAUAUA G GGAC GCGG U GCGCUACCCCAACACAAGAUGGUC GCCG GCGCUGA GCGCUACCC A GCGCUACCCC AC GCG C GCGC A G G G C G GGA
样例输出 3
1 0 1 2 3 2 0