题目描述

小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题： 给定 $n$ 个字符串二元组，第 $i (1 ≤ i ≤ n)$ 个字符串二元组为 ($s_{i,1}, s_{i,2}$)，满足$|s_{i,1}| = |s_{i,2}|$，其中 $|s|$ 表示字符串 $s$ 的长度。 对于字符串 $s$，定义 $s$ 的替换如下： • 对于 $s$ 的某个子串 $y$，若存在 $1 ≤ i ≤ 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 ≤ j ≤ m)$ 个问题会给定两个不同的字符串 $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 ≤ i ≤ n)$ 行包含两个字符串 $s_{i,1}, s_{i,2}$，表示第 $i$ 个字符串二元组。 输入的第 $j + n + 1 (1 ≤ j ≤ q)$ 行包含两个字符串 $t_{j,1}, t_{j,2}$，表示小 W 提出的第 $j$个问题。

输出

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

输入样例

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

输出样例

2
0

提示

【样例 1 解释】 对于小 W 的第一个询问，共有 $2$ 种 $t_{1,1}$ 的替换能够得到 $t_{1,2}$：

1. 令 $x, z$ 均为空串，$y = xabcx$，$i = 1$，则 $y′ = xadex$，替换后得到 $xadex$；
2. 令 $x = xa，y = bc，z = x，i = 3$，则 $y′ = de$，替换后得到 $xadex$。 【样例 2 输入】

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

【样例 2 输出】

0
0
0
0

【数据范围】 设 $L_1 =\sum_{i=1}^{n}|s_{i,1}| + |s_{i,2}|$，$L2 =\sum_{j-1}^{q}|t_{j,1}| + |t_{j,2}|$。对于所有测试数据，保证： • $1 ≤ n$, $q ≤ 2 × 10^5$； • $2 ≤ L_1$, $L_2 ≤ 5 × 10^6$； • 对于所有 $1 ≤ i ≤ n$，$s_{i,1}$, $s_{i,2}$ 均仅包含小写英文字母，且 $|s_{i,1}| = |s_{i,2}|$； • 对于所有 $1 ≤ j ≤ q$，$t_{j,1}$, $t_{j,2}$ 均仅包含小写英文字母，且 $t_{j,1}≠ t_{j,2}$。

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

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

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。