在南极的科考工作结束后，跳蚤国王成功了解了南极企鹅的习性。

具体地，跳蚤国王发现，在整个南极中，生活着 $n$ 只高智慧企鹅。这些企鹅也学习了人类，为自己取了一个独一无二的名字。具体地，对于每个 $1 \le i \le n$，第 $i$ 只企鹅的名字为一个仅由小写英文字母组成的字符串 $s_i$。为了避免指代关系的混淆，任意两只企鹅的名字都是不同的。

在接下来的 $m$ 天中，这些企鹅会聚集在一起玩游戏。具体地，在当天，企鹅们会一起商讨出一个同样仅由小写英文字母构成的字符串 $t$。随后，第 $i$ 只企鹅将会计算出 $c_i$，表示它的名字 $s_i$ 在字符串 $t$ 中出现的次数。在游戏的最后，如果所有企鹅都得到了正确的答案，那么他们便会感到非常高兴。

显然，企鹅们并不能理解字符串理论，因此他们并没有很好的方法来检验每个人的计算是否正确。因此，企鹅们决定在每一天结束后，计算出 $V = \displaystyle \sum_{i=1}^n 3^{i \times c_i} \bmod {2^{32}}$，作为他们当天计算结果的一个哈希值。这样在若干年以后，他们便可以等到未来他们都会字符串理论的时候，通过跟正确的哈希值比较，来猜测他们是否每个人都算对了。

经过科考团队的努力，科考团已经成功得到了每个企鹅的名字 $s_1, s_2, \cdots, s_n$ 与企鹅们每天选定的字符串。跳蚤国王对这些企鹅们游戏的过程非常感兴趣，因此他要求伏特检验这些企鹅们到底有没有计算正确。虽然伏特希望跳蚤国王别急，但是跳蚤国王还是很急，因此伏特没有时间等到未来的科技了。伏特请求你，计算出每天企鹅进行游戏后，假设每个企鹅都计算正确的情况下，所应得到的哈希值 $V$。

输入格式

输入的第一行包含一个正整数 $T$，表示子任务编号。

输入的第二行包含两个整数 $n, m$。

接下来 $n$ 行，每行一个字符串 $s_i$，表示第 $i$ 只企鹅的名字。保证 $s_i$ 互不相同。

接下来 $m$ 行，每行一个字符串 $t_j$，表示第 $j$ 天企鹅们选定的字符串。

输出格式

输出 $m$ 行，每行一个非负数，表示每个询问的答案。请注意答案需要对 $2^{32}$ 取模。

样例一

input

1
5 5
ab
b
a
ba
aa
a
ab
aba
abab
ababa

output

31
41
823
901
26335

explanation

五只企鹅的名字分别是 ab、b、a、ba、aa。

在第一天，企鹅们选定的字符串为 $t = \mathtt{a}$，企鹅们计算出的结果分别为 $c_1 = 0, c_2 = 0, c_3 = 1, c_4 = 0, c_5 = 0$。答案即为 $3^{1 \times 0} + 3^{2 \times 0} + 3^{3 \times 1} + 3^{4 \times 0} + 3^{5 \times 0} = 31$。

在第二天，企鹅们选定的字符串为 $t = \mathtt{ab}$，企鹅们计算出的结果分别为 $c_1 = 1, c_2 = 1, c_3 = 1, c_4 = 0, c_5 = 0$。答案即为 $3^{1 \times 1} + 3^{2 \times 1} + 3^{3 \times 1} + 3^{4 \times 0} + 3^{5 \times 0} = 41$。

在第三天，企鹅们选定的字符串为 $t = \mathtt{aba}$，企鹅们计算出的结果分别为 $c_1 = 1, c_2 = 1, c_3 = 2, c_4 = 1, c_5 = 0$。答案即为 $3^{1 \times 1} + 3^{2 \times 1} + 3^{3 \times 2} + 3^{4 \times 1} + 3^{5 \times 0} = 823$。

在第四天，企鹅们选定的字符串为 $t = \mathtt{abab}$，企鹅们计算出的结果分别为 $c_1 = 2, c_2 = 2, c_3 = 2, c_4 = 1, c_5 = 0$。答案即为 $3^{1 \times 2} + 3^{2 \times 2} + 3^{3 \times 2} + 3^{4 \times 1} + 3^{5 \times 0} = 901$。

在第五天，企鹅们选定的字符串为 $t = \mathtt{ababa}$，企鹅们计算出的结果分别为 $c_1 = 2, c_2 = 2, c_3 = 3, c_4 = 2, c_5 = 0$。答案即为 $3^{1 \times 2} + 3^{2 \times 2} + 3^{3 \times 3} + 3^{4 \times 2} + 3^{5 \times 0} = 26335$。

样例二

见附件下载。该样例满足子任务 2 的限制。

样例三

见附件下载。该样例满足子任务 3 的限制。

数据范围

令 $L = \max(\sum_{i = 1} ^ n |s_i|, \sum_{j = 1} ^ m|t_j|)$。

对于所有数据，$1\leq n, m\leq 2\times 10 ^ 5,\ 1 \leq |s_i| \leq 2\times 10 ^ 5,\ 1\leq |t_j|\leq 2\times 10 ^ 5,\ L\leq 2\times 10 ^ 6$。

特殊性质：将 $s_i$ 按长度从小到大排序，则 $s_i$ 是 $s_{i + 1}(1\leq i < n)$ 的前缀。

时间限制：$5\texttt{s}$

空间限制：$1\texttt{GB}$