题目描述

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

形式化地说，压缩算法会存储一个包含 $n$ 个字符串的字典 $s$，而数据是用一个序列 $a$ 表示的，数据解压后的内容为 $s_{a1}+s{a2}+\ldots+s{a_m}$。

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

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

下面形式化地给出题意：给定 $n$ 个字符串 $s_i$ 和 $m$ 个 $1 \sim n$ 之间的整数 $ai$，令母串为 $s{a1}+s{a2}+\ldots+s{a_m}$，回答 $q$ 次询问，每次给出一个字符串 $qs_i$，询问这个串在母串中的出现次数。请注意 $s_i$ 和 $qs_i$ 都只由字母 a,b 组成。

输入格式

从标准输入读入数据。

输入第一行包含三个正整数 $n,m,q$，保证 $1\le n,m,q\le 5\times 10^4$。

接下来 $n$ 行，每行一个字符串，表示 $s_i$。

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

接下来 $q$ 行，每行一个字符串，表示 $qs_i$。

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

保证 $\sum_{1\leq i\leq n} |si|,\sum{1\leq i\leq q} |qs_i| \le 10^5$。

输出格式

输出到标准输出。

输出 $q$ 行，每行一个整数，表示每个询问的答案。

样例

input

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

output

1
0
0
0
0
0
0
1
2
1

见附加文件中的 2.in/out。

数据范围与提示

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

$1\le n,m,q\le 5\times 10^4$。

$\sum_{1\leq i\leq n} |si|,\sum{1\leq i\leq q} |qs_i| \le 10^5$。