小 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≤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≤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 的替换的数量。

样例二：
输入：
3 4
a b
b c
c d
aa bb
aa b
a c
b a
输出：
0
0
0
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。

其余样例：replace.zip

CSP-S 2025 第三题