Out of context

It is election season and political speeches are everywhere. Your friend, an armchair pundit, likes to take quotes from politicians and use them out of context. You want to help that friend by building a way to search text for a given pattern.

One powerful way to express a text search pattern is a context-free grammar (CFG). A CFG generates strings and is defined as a 4-tuple $(V, \Sigma, R, S)$, where $V$ is a set of variables, $\Sigma$ is a set of terminal symbols, $S \in V$ is the starting variable, and $R$ is a set of rules. Each rule in $R$ has the form

$V \to (V \cup \Sigma)^*$

The head of a rule (the variable to the left of the arrow) can be replaced, wherever it appears, by the rule's production, which is the sequence of variables and terminal symbols to the right of the arrow. The right side of a rule may be empty, which means the variable on the left can be replaced by the empty string.

A grammar generates a string of terminals by derivation. A derivation begins with the sequence that holds just the start variable. Until every variable is gone, repeatedly replace any variable in the current sequence by any one of that variable's rules.

For example, here are the rules of a grammar with start variable A (above) and one derivation in that grammar (below).

A → CFG
C → CC
C → context
F → free
F → FF
G → grammar

A ⇒ CFG
⇒ CCFG
⇒ CcontextFG
⇒ CcontextFFG
⇒ CcontextFFgrammar
⇒ CcontextfreeFgrammar
⇒ contextcontextfreeFgrammar
⇒ contextcontextfreefreegrammar

Write a program that searches text for substrings a given CFG can generate.

In this problem $V$ is the set of English uppercase letters and $\Sigma$ is the set of English lowercase letters. The input begins with $R$, the rules of the CFG. The first line holds an integer $n$, the number of rules that follow ($1 \le n \le 30$). Each of the next $n$ lines describes one rule in the format

[A-Z] -> [a-zA-Z]*

That is, one uppercase letter, a single space, an arrow, a single space, and a string of zero or more uppercase and lowercase letters. A rule production is at most 10 characters long. The start variable $S$ is the head of the first rule.

After the rules come at most 100 lines of text to search, each at most 50 characters long. Every such line holds only English lowercase letters and spaces, and a line may be blank or hold only spaces. The input ends at end of file.

For each line to search, print on one line the longest non-empty substring the grammar can generate. If several substrings tie for longest, print the one that appears earliest in the line. If there is no such substring, print NONE in capital letters.