题目背景

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

提交了也是零分

题目描述

小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题：

给定 $n$ 个字符串二元组，第 $i$ ($1 \leq i \leq n$) 个字符串二元组为 $(s_{i,1}, s_{i,2})$，满足 $|s_{i,1}| = |s_{i,2}|$，其中 $|s|$ 表示字符串 $s$ 的长度。

对于字符串 $s$，定义 $s$ 的替换如下：

• 对于 $s$ 的某个子串 $y$，若存在 $1 \leq i \leq n$ 满足 $y = s_{i,1}$，则将 $y$ 替换为 $y' = s_{i,2}$。具体地，设 $s = x + y + z$，其中 $x$ 和 $z$ 可以为空，“+” 表示字符串拼接，则 $s$ 的替换将得到字符串 $s' = x + y' + z$。

小 W 提出了 $q$ 个问题，第 $j$ ($1 \leq j \leq q$) 个问题会给定两个不同的字符串 $t_{j,1}, t_{j,2}$，她想知道有多少种字符串 $t_{j,1}$ 的替换能够得到字符串 $t_{j,2}$。两种 $s$ 的替换不同当且仅当子串 $y$ 的位置不同或用于替换的二元组 $(s_{i,1}, s_{i,2})$ 不同，即 $x, z$ 不同或 $i$ 不同。你需要回答小 W 提出的所有问题。

输入格式

输入的第一行包含两个正整数 $n, q$，分别表示字符串二元组的数量和小 W 提出的问题的数量。

输入的第 $i+1$ ($1 \leq i \leq n$) 行包含两个字符串 $s_{i,1}, s_{i,2}$，表示第 $i$ 个字符串二元组。

输入的第 $j+n+1$ ($1 \leq j \leq q$) 行包含两个字符串 $t_{j,1}, t_{j,2}$，表示小 W 提出的第 $j$ 个问题。

输出格式

输出 $q$ 行，其中第 $j$ ($1 \leq j \leq q$) 行包含一个非负整数，表示替换后得到字符串 $t_{j,2}$ 的字符串 $t_{j,1}$ 的替换的数量。

输入输出样例 #1

输入 #1

4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

输出 #1

2
0

输入输出样例 #2

输入 #2

3 4
a b
b c
c d
aa bb
aa b
a c
b a

输出 #2

0
0
0
0

说明/提示

【样例 1 解释】

对于小 W 的第一个询问，共有 $2$ 种 $t_{1,1}$ 的替换能够得到 $t_{1,2}$:

1. 令 $x, z$ 均为空串，$y = \text{xabcx}$, $i = 1$，则 $y' = \texttt{xadex}$，替换后得到 $\text{xadex}$；
2. 令 $x = \texttt{xa}$, $y = \texttt{bc}$, $z = \texttt{x}$, $i = 3$，则 $y' = \texttt{de}$，替换后得到 $\texttt{xadex}$。

【样例 3】

见选手目录下的 $replace/replace3.in$ 与 $replace/replace3.ans$。

该样例满足测试点 11, 12 的约束条件。

【样例 4】

见选手目录下的 $replace/replace4.in$ 与 $replace/replace4.ans$。

该样例满足测试点 15, 16 的约束条件。

【数据范围】

设 $L_1 = \sum_{i=1}^{n} |s_{i,1}| + |s_{i,2}|$, $L_2 = \sum_{j=1}^{q} |t_{j,1}| + |t_{j,2}|$。对于所有测试数据，保证:

• $1 \leq n, q \leq 2 \times 10^5$;
• $2 \leq L_1, L_2 \leq 5 \times 10^6$;
• 对于所有 $1 \leq i \leq n$, $s_{i,1}, s_{i,2}$ 均仅包含小写英文字母，且 $|s_{i,1}| = |s_{i,2}|$;
• 对于所有 $1 \leq j \leq q$, $t_{j,1}, t_{j,2}$ 均仅包含小写英文字母，且 $t_{j,1} \neq t_{j,2}$。

::cute-table{tuack}

测试点编号	$n, q \leq$	$L_1, L_2 \leq$	特殊性质
$1, 2$	$10^2$	$200$	无
$3 \sim 5$	$10^3$	$2\,000$	^
$6$	^	$10^6$	AB
$7, 8$	$10^4$	^	A
$9, 10$	$2 \times 10^5$		B
$11, 12$	^	$2 \times 10^6$	无
$13, 14$		$5 \times 10^6$	A
$15, 16$		^	B
$17 \sim 20$			无

特殊性质 A：$q = 1$。

特殊性质 B：定义字符串 $s$ 为特别的，当且仅当字符串 $s$ 仅包含字符 $a$ 和 $b$，且字符 $b$ 在 $s$ 中出现恰好一次。对于所有 $1 \leq i \leq n$, $s_{i,1}, s_{i,2}$ 均为特别的，且对于所有 $1 \leq j \leq q$, $t_{j,1}, t_{j,2}$ 均为特别的。