E. Abu Adel's Nokia 3311
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abu Adel, the famous storyteller at Abu Hatem's coffee shop, decided to write his own fictional stories and sell them. So, he went and bought a magical Nokia 3311 to write stories faster.

The magical Nokia 3311 has $$$k$$$ keys, each of which is used to type several characters. Each lowercase English letter is assigned to exactly one key.

Nokia 3311*

Abu Adel authored an amazing fictional story about smartphones that use touch screens instead of keys. However, despite writing a remarkable story, he forgot to save his work, and all of it was lost.

Fortunately, he has a key logger. By reviewing the logs, he hopes to retrieve the original text.

Abu Adel knows $$$n$$$ English words. When he examined the logs, he found that he had written $$$m$$$ words, but for each word, he only knows the pattern of the keys he pressed rather than the exact characters.

Now, for each of the $$$m$$$ patterns, Abu Adel wants to determine how many of the $$$n$$$ words he knows can be formed using that pattern. This will help him narrow down the possibilities and recover the original text.

Input

The first line contains three integers $$$k$$$ $$$(1 \le k \le 10)$$$, $$$n$$$ $$$(1 \le n \le 10^5)$$$, and $$$m$$$ $$$(1 \le m \le 10^5)$$$ — denoting the number of keys, the number of words Abu Adel knows, and the number of words in the logger, respectively.

The input will then contain $$$k$$$ lines, one for each digit from $$$0$$$ to $$$k-1$$$ respectively.

Each line will contain a string $$$s$$$ $$$(1 \leq |s| \leq 26)$$$, where $$$s$$$ is either a "#" (indicating that the key is not mapped to any lowercase English letter) or a string of distinct lowercase English letters representing the characters mapped to the current key.

Note: It is guaranteed that each of the 26 lowercase English letters is mapped to exactly one key.

The next $$$n$$$ lines each contain a string $$$w$$$ $$$(1 \le |w_i| \le 10^5)$$$ — where $$$w_i$$$ denotes the $$$i_{th}$$$ word that Abu Adel knows. It is guaranteed that all characters in $$$w_i$$$ are lowercase English letters only.

The next $$$m$$$ lines each contain a string $$$p$$$ $$$(1 \le |p_i| \le 10^5)$$$ — where $$$p_i$$$ denotes the $$$i_{th}$$$ pattern in the log file. It is guaranteed that $$$p$$$ consists only of digits from $$$0$$$ to $$$k-1$$$.

It is also guaranteed that the sum of $$$|w_i|$$$ across all words Abu Adel knows is less than $$$10^6$$$, and the sum of $$$|p_i|$$$ across all patterns is less than $$$10^6$$$.

Output

Print $$$m$$$ integers, where the $$$i_{th}$$$ integer represents the number of words that match the $$$i_{th}$$$ pattern.

Examples
Input
10 4 3
abc
#
defg
hijklm
nop
qrs
#
tuv
wxy
z
moon
hello
hija
lnop
3444
32334
3330
Output
2
1
1
Input
1 2 3
abcdefghijklmnopqrstuvwxyz
hello
moon
00000
0000
000
Output
1
1
0
Note