Problem E
Context-Free Grammar Parsing

Given as input a context-free grammar (CFG) and a list of strings, indicate whether each string could be generated by the grammar. For this problem, the grammar is in a (very slightly) restricted version of Chomsky normal form (CNF).

The grammar use production rules of the following form:

where $V$ is a set of variables and $\Sigma $ is a set of symbols. In other words, each rule indicates that one variable can produce either one symbol or two more variables.

Chomsky normal form further requires that the start variable appears nowhere in any rule production (the right hand side of a rule). In this problem, no rule may produce $\varepsilon $ (the empty string), which is why this is a restricted version of CNF.

In case you need a refresher, a CFG produces a string of (only) symbols by the following algorithm:

• Start with only the starting variable.

• Replace any variable with its production.

• Repeat from step 2 until only symbols remain.

We say that the language of the grammar is all the strings that can be produced in this way by the grammar.

Input

Input starts with a description of a grammar in restricted CNF. The first line contains an integer $n$, indicating the number of rules that follow. The following $n$ lines each contain one rule. Each rule begins with a variable, then a single space, then either a single symbol or a pair of variables. For this problem, a variable is an upper-case letter (A–Z), and a symbol is a lowercase letter (a–z). The start variable of the grammar is the first variable in the first rule of the grammar.

After the grammar is a line containing an integer $s$ indicating the number of strings to test. Each of the following $s$ lines contains a string $t$ containing only lowercase English letters (a–z).

Output

For each of the $s$ strings, output ‘yes’ if it is in the language of the grammar, or ‘no’ otherwise.

Scoring

Your program will be tested on a set of test groups, each of which is worth a number of points. Each test group contains several test cases, and to receive the points for a test group your program must solve all of the test cases in that group. The score of your program is the sum of the points received on all of the test groups.

4
S AB
A a
B BB
B b
3
abb
abbbb
bbbb

yes
yes
no