For the first time the Skyrim Free School of Mathematics, Philosophy and Linguistics will host
the Regular Expressions (regex) Contest (RegExCon). The contest happens this way: participants
compete always against 1 opponent. One wins one loses. Only one will remain, the champion. In one
dispute both participants receive a list with several regular expressions and for each regex the
participants must calculate if several given words are recognized or not by the regex. As a member of
the School you are participating, and want to win.
So, to guarantee your victory, you have to write a program to solve the problem and let it
executing in your Cool Stuff Calculator Machine at home. As a mage, expert in Alteration and Illusion,
you can easily control your machine with your mind, so you can use your program while in the contest.
It's forbidden to use magic in the contest, but coincidentally the Winterhold School will host some
Mage Congress, so you don't need to worry, use your magic.
A regular expression is used to describe a language (a set of words). Consider that the alphabet
of all languages in this problem is {a, b}.
A regex R is valid if:
1) R is “a” or “b”;
2) R is “(P.S)” where P and S are regular expressions;
3) R is “(P|S)” where P and S are regular expressions;
4) R is “(P*)” where P is a regular expression;
Regular expressions can be nested. There is no ternary operation with operators “.” and “|”,
neither binary operation with operator “*”. Words always start with “(“ and finish with “)”.
Set L of words recognized by R is formed following next rules:
1) If R is “(a)”, L = {a};
2) If R is “(b)”, L = {b};
3) If R is “(P.S)”, L = all words that can be obtained from a concatenation of words p and s,
where p is recognized by P and s by S;
4) If R is “(P|S)”, L = union of the sets of words recognized by P and S;
5) If R is “(P*)”, R recognizes the concatenation of 0 or more words recognized by P.

Input

Input file contains several test cases. First line of a test case contains a regex (defined before, between 1 and 150). Next line
contain an integer P (1 ≤ P ≤ 100). Each one of the next P lines contains a word formed by 'a's and 'b's (<= 50)
that represents the following question: “Is this word recognized by the given regex?”.

Output

For each question described before, answer “Y” (no quotes) if the answer is “yes” or “N” (no quotes) if
the answer is “not”. At the end of each test case print a blank line.

Example

Input:
(a)
3
a
b
aa
(a.b)
3
a
ab
b
(a|b)
4
a
b
ab
ba
(a*)
3
a
aaaaaaaaaaa
aaaaabaaaaa
((a*).(b*))
3
bbbaaa
aaabbb
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
Output:
Y
N
N
N
Y
N
Y
Y
N
N
Y
Y
N
N
Y
Y