Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3440
Detect the Virus II

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

A virus is a sequence of letters that can be matched in the virus database.

Nowadays, viruses become complex. They have varieties. Fortunately, the database has the ability to precisely describe all varieties of viruses.

The database describes viruses using text records. A text record has the form

identification_label:=content

This define identification_label as content. The identification_label consists of lower-case letters (at least one letter). The content has four forms:

  • lower-case letters
    This content is exactly a sequence of letters (at least one letter), which is usually a part of virus.
  • [identification_label]
    This content is defined in the record with matched identification_label.
  • content1content2
    This content has two parts: content1, followed by content2. No '|' is allowed in content1 and content2.
  • content1|content2
    This content is either content1 or content2.

The virus is defined with the identification "virus".

It is guaranteed no recursive records. An illegal example:

virus:=[b]
b:=[a]
a:=[b]

This is not legal, either:

virus:=[virus]

This is legal:

parta:=a|b|c
virus:=[parta][partb][partb]
partb:=d|e[subparta]h
subparta:=fg|g

add, cdefgh can be matched using above records. They are regarded as virus.

Input

Input has at most 10 test cases, separated by one blank line.

Each case begins with an integer N, followed by N (1 ≤ N ≤ 12) lines of text records describing the virus. Then an integer M, followed by M (1 ≤ M ≤ 30) lines. Each line has one virus sample, which is a sequence of lower-case letters, may contain virus and is to be detected.

Each identification_label has 32 letters at most. Each content has 128 characters at most. Each virus sample has 2048 characters at most.

In one case, content of records are mostly just simple letters or [identification_label] (1st or 3rd form). Test cases are somehow simple enough to prevent you from Time Limit Exceed. Take it easy.

Output

For each virus sample, if the virus can be detected, output YES, otherwise output NO.

Output one blank line AFTER each test case.

Sample Input

4
parta:=a|b|c
virus:=[parta][partb][partb]
partb:=d|e[subparta]h
subparta:=fg|g
2
abcdefghijklm
nopqrstuvwxyz

Sample Output

YES
NO


Author: WU, Jun
Contest: Let's Celebrate the 100th Contest on ZOJ!
Submit    Status