题目描述

给定一个由 N 个单词组成的词典 W_1, W_2, ..., W_N。这些单词只包含大写字母集合 {A, C, G, U}。

此外，还有 Q 个关于词典的查询。每个查询给定两个字符串 P_i 和 S_i，要求统计满足以下条件的单词数量：

• 该单词的前 |P_i| 个字符恰好等于 P_i；
• 该单词的后 |S_i| 个字符恰好等于 S_i。

请编写程序 dictionary 来回答这些查询。

这里 |X| 表示字符串 X 的长度。

输入格式

第一行输入两个正整数 N 和 Q，分别表示词典中的单词数和查询数。

接下来 N 行，每行输入一个单词 W_i。

最后 Q 行，每行输入两个字符串 P_i 和 S_i，表示一次查询。

输出格式

输出 Q 行。

第 i 行输出一个整数，表示第 i 个查询的答案。

数据范围

• 1 <= N, Q <= 10^5
• 1 <= |W_i|, |P_i|, |S_i| <= 10^5
• |W_1| + |W_2| + ... + |W_N| <= Sum
• |P_1| + |P_2| + ... + |P_Q| <= Sum
• |S_1| + |S_2| + ... + |S_Q| <= Sum
• Sum = 2 × 10^6
• 所有字符串都只由 {A, C, G, U} 中的字符组成

子任务

只有当某个子任务及其依赖子任务的所有测试点全部通过时，才可获得该子任务分数。

样例

样例 1

输入

2 3
AUGC
AGC
G C
AU C
A C

输出

0
1
2

解释

• 第 1 个查询对应的集合为 {}。
• 第 2 个查询对应的集合为 {AUGC}。
• 第 3 个查询对应的集合为 {AUGC, AGC}。

样例 2

输入

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

输出

2
1
1

样例 3

输入

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA

输出

1
0
1
2
3
2
0