B. Fim4

内存限制:2048 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

黎瑟最近在机器遗忘平台 IQ-- 上租了一台服务器来训练她的梯度上升算法,服务器上存着很大的数据集。由于这些数据集里大部分数据都有很大的相似性,所以这些数据都以一种压缩比很高的方式压缩了起来。

形式化地说,压缩算法会存储一个包含 nn 个字符串的字典 ss ,而数据是用一个序列 aa 表示的,数据解压后的内容为 sa1+sa2++sams_{a_1}+s_{a_2}+\cdots+s_{a_m}

黎瑟本地硬盘的空间并不富裕,网络条件也不好,因此她只能不断向服务器发送请求,每次询问一个字符串 qsiqs_i 在数据中的出现次数。

但数据解压后的长度实在太大,普通的朴素算法无法工作,为了让她顺利的把实验数据给你写论文,帮她实现这个算法吧。

下面形式化地给出题意:给定 nn 个字符串 sis_imm1n1 \sim n 之间的整数 aia_i,令母串为 sa1+sa2++sams_{a_1}+s_{a_2}+\cdots+s_{a_m},回答 qq 次询问,每次给出一个字符串 qsiqs_i,询问这个串在母串中的出现次数。请注意 sis_iqsiqs_i 都只由字母 a,b 组成。

输入格式

从标准输入读入数据。

输入第一行包含三个正整数 n,m,qn,m,q,保证 1n,m,q5×1041\le n,m,q\le 5\times 10^4

接下来 nn 行,每行一个字符串,表示 sis_i

接下来一行 mm 个正整数,表示 aia_i。保证1im,1ain\forall 1\leq i\leq m,1\le a_i\le n

接下来 qq 行,每行一个字符串,表示 qsiqs_i

保证读入的所有字符串都只由字符a,b组成。

保证1insi,1iqqsi105\sum_{1\leq i\leq n} |s_i|,\sum_{1\leq i\leq q} |qs_i| \le 10^5

输出格式

输出到标准输出。

输出 qq 行,每行一个整数,表示每个询问的答案。

样例

样例输入 1

10 5 10
b
aa
b
bbb
aaa
ba
ba
bb
ba
a
6 5 5 1 5 
aba
bbabbabba
bb
aabbbaabb
bbbbbbbbb
bbbbaab
babbbba
aaaaaba
b
baaaaa

样例输出 1

1
0
0
0
0
0
0
1
2
1

样例2

见附加文件中的 2.in2.out

数据范围与提示

本题使用捆绑测试。每个子任务有若干个测试点,分为 44 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

1n,m,q5×1041\le n,m,q\le 5\times 10^4

1insi,1iqqsi105\sum_{1\leq i\leq n} |s_i|,\sum_{1\leq i\leq q} |qs_i| \le 10^5

子任务 分值 特殊性质
1 20 1imlen(sai)106 \sum_{1\leq i\leq m} len\left (s_{a_i}\right ) \le 10^6
2 20 max{len(qsi)}min{len(si)} \max \{ len\left( qs_{i}\right ) \} \le \min \{ len \left (s_i \right ) \}
3 30 max{len(qsi)}200 \max \{ len \left ( qs_{i}\right ) \} \le 200
4 30