给定 $n$ 条有向替换规则 $(s_{i,1},s_{i,2})$，每条规则左右两侧的字符串长度相等。

一次替换中，选择源字符串的一段连续子串；若它恰好等于某条规则的左侧，则将它替换为该规则的右侧，其余位置保持不变。

每个询问给出两个不同字符串，求将第一个字符串通过恰好一次替换变成第二个字符串的方法数。替换位置不同或规则编号不同均视为不同方法；重复规则也要分别计数。规则不能反向使用，也不能连续进行多次替换。两个询问字符串的长度可能不同。

输入格式

第一行包含两个整数 $n,q$。

接下来 $n$ 行，每行给出一条规则的两个字符串。随后 $q$ 行，每行给出一个询问的两个字符串。所有字符串均为非空小写字母串。

输出格式

对每个询问输出一行一个整数，表示可行的替换方法数。

样例 1

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

2
0

样例 2

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

0
0
0
0

数据范围与原题特殊限制

$L_1$ 为全部替换规则左右两侧字符串长度之和，$L_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}$。

测试点编号	$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}$ 均为特别的。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。