Mhocskian Languages

Time limit2sMemory limit512 MB

Summary

Given a context-free grammar in Chomsky normal form and a list of words, decide for each word whether the start variable can derive it.

Level: Medium7 of 10
Topics: Dynamic programming, String, Implementation, Backtracking
Solved: No attempts yet

Problem

Linguists are studying Mhocskian, the language of the native inhabitants of Mhocsky Island. They have found a description of how the natives build words, together with a list of candidate words, and want to know which of those words are valid Mhocskian words.

Words in Mhocskian are built from two kinds of symbols.

A variable is an uppercase letter used only while a word is being built.
A terminal is a lowercase letter that actually appears in a finished word.

There are two kinds of rules.

$V \rightarrow V_1 V_2$ replaces the variable $V$ with the two variables $V_1 V_2$ , in that order.
$V \rightarrow t$ replaces the variable $V$ with the terminal $t$ .

One of the variables is the start variable. A word $w$ made up of lowercase letters is a valid Mhocskian word if, starting from the start variable, some sequence of rule applications produces exactly $w$ . For instance, if the start variable is $S$ with rules $S \rightarrow AB$ , $A \rightarrow a$ , and $B \rightarrow b$ , then applying $S \rightarrow AB$ , then $A \rightarrow a$ and $B \rightarrow b$ derives the word $ab$ , so $ab$ is valid.

Given the rules and a list of words, decide for each word whether it is a valid Mhocskian word.

Input

The first line contains two integers $V$ and $T$ : the number of variables and the number of terminals.
The second line contains $V$ space-separated uppercase letters, the variables. The first of them is the start variable.
The third line contains $T$ space-separated lowercase letters, the terminals.
The fourth line contains an integer $R_1$ . Each of the next $R_1$ lines has the form V t and represents a rule $V \rightarrow t$ .
The next line contains an integer $R_2$ . Each of the next $R_2$ lines has the form V V1 V2 and represents a rule $V \rightarrow V_1 V_2$ .
The next line contains an integer $W$ . Each of the next $W$ lines contains one word made entirely of lowercase letters.

Output

Output $W$ lines. On line $i$ , print 1 if the $i$ -th word is a valid Mhocskian word, and 0 otherwise.

Constraints

$1 \le V, T \le 26$
$1 \le R_1 + R_2 \le 30$
$1 \le W \le 20$
Each word in the list has length between $1$ and $30$ .

Examples4

Example 1

Input

5 2
I S A B C
a b
2
A a
B b
7
I A B
I A C
C S B
S A B
S A C
I S S
S S S
4
abababaaabbbaabbaabb
abab
bbaa
aaabababbaaabbbb

Expected output

Example 2

Input

3 2
S A B
a b
3
S a
A a
B b
1
S A B
3
ab
a
b

Expected output

1
1
0

Example 3
Input
```
1 1
S
a
1
S a
0
2
a
aa
```
Expected output
```
1
0
```

Example 4

Input

4 2
S X Y Z
a b
4
S a
X a
Y b
Z b
2
S X Y
S S S
8
a
b
ab
ba
aab
abab
abb
baa

Expected output