Lise recently rented a server on the machine-forgetting platform IQ-- to train her gradient ascent algorithm, and the server contains a very large dataset. Since most of the data in these datasets share high similarity, they are stored using a high-compression-ratio format.
Formally, the compression algorithm stores a dictionary $s$ containing $n$ strings, and the data is represented by a sequence $a$. The decompressed content of the data is $s_{a_1}+s_{a_2}+\ldots+s_{a_m}$.
Lise's local hard drive space is limited, and network conditions are poor, so she can only send requests to the server, asking for the number of occurrences of a string $qs_i$ in the data each time.
However, the length of the decompressed data is too large for naive algorithms to work. To help her successfully write her paper with the experimental data, please implement this algorithm for her.
The problem is formally stated as follows: Given $n$ strings $s_i$ and $m$ integers $a_i$ between $1$ and $n$, let the master string be $s_{a_1}+s_{a_2}+\ldots+s_{a_m}$. Answer $q$ queries, where each query provides a string $qs_i$ and asks for the number of occurrences of this string in the master string. Note that $s_i$ and $qs_i$ consist only of the letters a and b.
Input
The first line contains three positive integers $n, m, q$, where $1 \le n, m, q \le 5 \times 10^4$.
The next $n$ lines each contain a string representing $s_i$.
The next line contains $m$ positive integers representing $a_i$. It is guaranteed that $\forall 1 \le i \le m, 1 \le a_i \le n$.
The next $q$ lines each contain a string representing $qs_i$.
It is guaranteed that all input strings consist only of the characters a and b.
It is guaranteed that $\sum_{1 \le i \le n} |s_i|, \sum_{1 \le i \le q} |qs_i| \le 10^5$.
Output
Output $q$ lines, each containing an integer representing the answer to each query.
Examples
Input 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
baaaaaOutput 1
1
0
0
0
0
0
0
1
2
1Input 2
See the provided files.
Subtasks
This problem uses bundled testing. There are 4 subtasks, each containing several test cases. You must pass all test cases in a subtask to receive the points for that subtask.
$1 \le n, m, q \le 5 \times 10^4$.
$\sum_{1 \le i \le n} |s_i|, \sum_{1 \le i \le q} |qs_i| \le 10^5$.
| Subtask | Score | Special Properties |
|---|---|---|
| 1 | 20 | $\sum_{1 \le i \le m} \text{len}(s_{a_i}) \le 10^6$ |
| 2 | 20 | $\max \{ \text{len}(qs_i) \} \le \min \{ \text{len}(s_i) \}$ |
| 3 | 30 | $\max \{ \text{len}(qs_i) \} \le 200$ |
| 4 | 30 | None |