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

具体地，跳蚤国王发现，在整个南极中，生活着 $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}mod{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\le n,m\le 2\times {10}^5,1\le |s_i|\le 2\times {10}^5,1\le |t_j|\le 2\times {10}^5,L\le 2\times {10}^6$。

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

时间限制：$5\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$