Description

上下文无关文法是一种强大的描述语言的方法。许多编程语言的语法，包括在这个在线评测系统上提供了编译器的C、C++、Java和Pascal，都是用上下文无关文法指定的。

在这个题目中，我们用一种生成式的观点来看待上下文无关文法。一个上下文无关文法由一组用以改写符号串的生成规则组成。每一条生成规则都有这样的形式：

V → w

其中V是一个符号，w是一个符号串。符号被分成终结符号和变元两种。在上面的规则里，V必须是一个变元，而w可以包含变元和／或终结符号。“上下文无关”表达出这样一个事实：V总是可以被替换成w，无论它在什么上下文中出现。在所有变元中，有一个被指定为开始变元。利用一个上下文无关文法生成一个串，首先要从包含单个开始变元的串开始，连续和任意得应用规则改写串，直到只剩下终结符号。

例如，字母表只包含z，开始变元是S，有下列规则：

1. S → CB
2. S → ZZ
3. A → CB
4. A → ZZ
5. B → ZZ
6. C → BA
7. Z → z

那么我们从S开始，然后选择一个规则来应用。如果我们选择规则1, 就将S替换成CB，得到串CB。然后，如果我们选择规则6，就将C替换成BA，得到串BAB。如果我们现在选择规则4，就将A替换成ZZ，得到串BZZB。我们可以用符号来更简洁的表示这一系列选择：S ⇒ CB ⇒ BAB ⇒ BZZB ⇒ ZZZZB ⇒ ZZZZZZ ⇒ zZZZZZ ⇒ zzZZZZ ⇒ zzzZZZ ⇒ zzzzZZ ⇒ zzzzzZ ⇒ zzzzzz。这个文法的语言就是所有由一个奇数的两倍那么多个z组成的串的集合。

给出一个上下文无关语言和一些串，判定这些串是否属于这个文法的语言。

Input

为简洁其见，我们将上下文无关文法中所有“→”左边的变元相同的的规则组合到一起。例如，我们将下面三条规则

S → u
S → v
S → w

组合成

S → u | v | w

上下文无关文法用一种称为Chomsky范式的特殊形式给出。用Chomsky范式给出的上下文无关文法只包含如下形式的规则：

A → BC
A → a

其中a是任意终结符号，A、B、和C是任意变元，但B和C不能是开始变元。Chomsky范式还允许规则S → ε, 其中S是开始变元，ε表示空串，使得上下文无关文法可以产生空串。在这个题目中我们忽略这种情况。

输入用Chomsky范式给出一个上下文无关文法和不超过50个串。我们用单个小写字母作为终结符号，当个大写字母作为变元。S总是被看作开始符号。文法用若干行给出。每一行包含按上述方式组合成的同一个变元的生成规则。“→”将会被替换成“->”。不是所有可能的变元都会在文法中出现，但每个出现的变元都会有至少一条规则。包含单个“#”的一行表示文法的结束。在文法后面，每行包含一个串。当再不能找到任何串时输入结束。空格和空行不会在输入中出现。

Output

为每个串输出一行。如果一个串属于给定的上下文无关文法的语言，输出“YES”（不包含括号），否则输出“NO”（不包含括号）。

S->CB|ZZ
A->CB|ZZ
B->ZZ
C->BA
Z->z
#
zzzzzz
z
a

YES
NO
NO

Source

第六届北京大学程序设计大赛暨ACM/ICPC选拔赛, frkstyc

Translator

Yingchong SITU 'frkstyc'