[JOI Open 2016] 销售基因链

题目背景

**译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T2 「RNA 鎖の販売 / Selling RNA Strands」** 本题由于测试数据过多,仅在此提供部分测试数据,剩余数据请[于此测试](https://www.luogu.com.cn/problem/U288877)。

题目描述

基因库中有 $N$ 个字符串,这些字符串仅由 `A`,`G`,`U`,`C` 组成(保证每个字符串都包含四种字母)。 有 $M$ 组查询,每组查询包含两个字符串 $P,Q$,试求:基因库中有多少个字符串同时存在前缀 $P$ 和后缀 $Q$。 举个例子,`GAC` 存在前缀 `G`、`GA`、`GAC`,存在后缀 `C`、`AC`、`GAC`,那么我们可以说:`GAC` 同时存在前缀 `GA` 和后缀 `AC`。

输入输出格式

输入格式


输入共 $N + M + 1$ 行。 第一行有两个整数 $N, M$。 在接下来的 $N$ 行中,每行一个字符串 $S_i$,表示基因库中的一个字符串。 在接下来的 $M$ 行中,每行有两个用空格分隔的字符串,表示一组查询。

输出格式


输出共 $M$ 行,每行一个整数,表示符合查询条件的字符串的数量。

输入输出样例

输入样例 #1

2 3
AUGC
AGC
G C
AU C
A C

输出样例 #1

0
1
2

输入样例 #2

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

输出样例 #2

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

输出样例 #3

1
0
1
2
3
2
0

说明

### 样例 1 解释 第一组查询:无法找到; 第二组查询:`AUGC` 满足条件; 第三组查询:`AUGC` 和 `AGC` 满足条件。 ### 样例 2 解释 注意基因库中的字符串可以重复。 ### 数据规模与约定 **本题采用捆绑测试**。 对于所有数据,$1\le N, M \leq 10 ^ 5$,$1 \leq |S_i|, |P_j|, |Q_j| \le 10^5$,$1\le\sum |S_i|, \sum |P_j|, \sum |Q_j| \le 2\times 10^6$。 - Subtask 1(10 points):$N, M, |S_i|, |P_j|, |Q_j| \le 100$。 - Subtask 2(25 points):$N, M\le 5000$。 - Subtask 3(25 points):$\sum |S_i|, \sum|P_j|, \sum |Q_j| \le 10^5$。 - Subtask 4(40 points):没有额外限制。