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