IPSC Logo

Internet Problem Solving Contest

IPSC 2009
Problem M - Muzidabutur

Muzidabutur is a very powerful magic phrase. For example, if you write the phrase on a monitor using a non-erasable marker, your local computer administrator will throw you into a waste bin (and we do not mean the folder). The problem is that nobody really remembers this phrase anymore.

The famous archeologist Alabama Steve recently discovered two ancient tomes. In one of them he found a short description of the Muzidabutur. He suspects that one of the sentences in the other tome is Muzidabutur. But the tome is way too thick and he does not have the time to process it by hand.

Problem specification

You are given a description of Muzidabutur, and N queries. For each query decide whether it can be the Muzidabutur.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with line containing a textual description of the Muzidabutur. You may assume that spaces and characters ‘(’ and ‘)’ will not occur inside strings and character sets used to define the Muzidabutur.

The next line contains N, which is the number of sentences in the second tome. Each of the next N lines contains one sentence.

Output specification

For each sentence output the string “YES” if it exactly matches the description of a Muzidabutur, and output “NO” otherwise.

Example

input
1

THE LETTER A FOLLOWED BY (ONE OF THE LETTERS abc OR THE STRING gg) AT LEAST 3 TIMES
4
Abggaggc
abbb
Abc
Hello, Abggaggc, how are you?

output
YES
NO
NO
NO

Note that the Muzidabutur is case sensitive, therefore the second sentence is not a Muzidabutur.
Also, the description must match the entire sentence, therefore the last sentence is not a Muzidabutur.