## CCO '12 P3 - Mhocskian Languages

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
##### 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 by two variables in that order, and we write as a short form for this type of rule. The second type of rule allows you to replace a variable by a terminal , and we write as a short form for this type of rule.

One of the variables is the start variable. A word 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 .

#### Example

Suppose we have variables , terminals , and rules

The word "" is a valid Mhocskian word because it can be constructed in the following way: . The word "" can be constructed simply by . The word "" cannot be constructed.

#### Input

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

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

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

On the fourth line, there is an integer . lines follow, each of which is of the form , representing a rule .

On the next line, there is an integer . lines follow, each of the form , representing the rule .

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

#### Output

The output must contain lines. On line , output a if the word is a valid Mhocskian word, and otherwise.

#### Constraints

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