Canadian Computing Competition: 2012 Stage 2, Day 1, Problem 3

Linguists are currently studying Mhocskian, the language of the native inhabitants of Mhocsky island. The linguists have found a description of how the natives construct words in Mhocskian, and a list of words. The linguists would now like to know which of the words in the list are valid Mhocskian words.

Rules

Words in Mhocskian are constructed according to a set of rules. These rules involve two types of components: variables and terminals. A variable is an uppercase letter used in the description of the rules. A terminal is a lowercase letter that is part of a Mhocskian word. Variables and terminals are just uppercase and lowercase letters, respectively, of the English alphabet.

There are two types of rules. The first type of rule allows you to replace a variable ~V~ by two variables ~V_1 V_2~ in that order, and we write ~V \to V_1 V_2~ as a short form for this type of rule. The second type of rule allows you to replace a variable ~V~ by a terminal ~t~, and we write ~V \to t~ as a short form for this type of rule.

One of the variables is the start variable. A word ~w~ is composed of lowercase letters from the English alphabet. It is a valid Mhocskian word if, starting from the start variable, it is possible to follow a sequence of rules to obtain ~w~.

Example

Suppose we have variables ~\{S, A, B\}~, terminals ~\{a, b\}~, and rules $$\displaystyle \{S \to AB, S \to a, A \to a, B \to b\}.$$

The word "~ab~" is a valid Mhocskian word because it can be constructed in the following way: ~S \to AB \to aB \to ab~. The word "~a~" can be constructed simply by ~S \to a~. The word "~b~" cannot be constructed.

Input

On the first line, two integers ~V~ and ~T~ in that order, denoting the number of variables and terminals, respectively, in Mhocskian.

On the second line, ~V~ space separated uppercase letters, the variables. The first variable on the line is always the start variable.

On the third line, ~T~ space separated lowercase letters, the terminals.

On the fourth line, there is an integer ~R_1~. ~R_1~ lines follow, each of which is of the form ~V~ ~t~, representing a rule ~V \to t~.

On the next line, there is an integer ~R_2~. ~R_2~ lines follow, each of the form ~V~ ~V_1~ ~V_2~, representing the rule ~V \to V_1 V_2~.

On the next line, there is an integer ~W~. ~W~ lines follow, each contains a single word made entirely of lowercase letters.

Output

The output must contain ~W~ lines. On line ~i~, output a ~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 of the words in the linguists' list will have length between 1 and 30.

Sample 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

Sample Output

1
1
0
1