7288 - 谐音替换（replace）

小 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 解释】

对于小 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}。

【数据范围】

设 $L1 = \sum{i=1}^{n} |s{i,1}| + |s{i,2}|, L2 = \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}$。

CSP