小 W 将谐音替换定义为以下字符串问题：给定 $n$ 个字符串二元组，第 $i$ 个二元组为 $(s_{i,1}, s_{i,2})$，满足 $|s_{i,1}| = |s_{i,2}|$。

对于字符串 $s$，定义 $s$ 的替换如下：对于 $s$ 的某个子串 $y$，若存在 $1 \le i \le n$ 满足 $y = s_{i,1}$，则将 $y$ 替换为 $y' = s_{i,2}$。即设 $s = x+y+z$（$x,z$ 可为空，"+"表示拼接），替换后得到 $s' = x+y'+z$。

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

注：原评测使用文件输入输出（replace.in / replace.out），本站提交请使用标准输入输出，程序中不要写文件重定向代码。原题提交文件名：replace.cpp，编译选项 -O2 -std=c++14 -static。

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

第 $i+1$（$1 \le i \le n$）行包含两个字符串 $s_{i,1}, s_{i,2}$。

第 $j+n+1$（$1 \le j \le q$）行包含两个字符串 $t_{j,1}, t_{j,2}$。

输出 $q$ 行，第 $j$ 行包含一个非负整数，表示替换后能得到 $t_{j,2}$ 的 $t_{j,1}$ 的替换数量。

【样例 1 解释】

第一个询问有 2 种替换：① $x,z$ 均为空，$y=xabcx$，$i=1$；② $x=xa$，$y=bc$，$z=x$，$i=3$。

【样例 2 输入】

3 4 / a b / b c / c d / aa bb / aa b / a c / b a（输出 4 行均为 0）

【数据范围】

设 $L_1 = \sum(|s_{i,1}|+|s_{i,2}|)$，$L_2 = \sum(|t_{j,1}|+|t_{j,2}|)$。

• $1 \le n, q \le 2 \times 10^5$；
• $2 \le L_1, L_2 \le 5 \times 10^6$；
• 字符串均仅含小写英文字母，$|s_{i,1}|=|s_{i,2}|$，$t_{j,1} \ne t_{j,2}$。

测试点 20 个等分。特殊性质 A：$q=1$；B：所有字符串仅含 a 和 b 且 b 恰好出现一次。

原题另有附加样例 replace3、replace4（已收录为本题测试点）。