UOJ Logo Universal Online Judge

UOJ

#772. 【UER #11】企鹅游戏

附件下载 统计

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

具体地,跳蚤国王发现,在整个南极中,生活着 $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

五只企鹅的名字分别是 abbabaaa

在第一天,企鹅们选定的字符串为 $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$。

子任务编号 $L\leq $ 特殊性质 分值
$1$ $5\times 10 ^ 3$ $20$
$2$ $2\times 10 ^ 6$ $20$
$3$ $3\times 10 ^ 5$ $30$
$4$ $2\times 10 ^ 6$ $30$

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

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

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