Is Regex Matching

For each query, decide whether the entire string matches the regex: a lowercase letter matches itself, . matches any one lowercase letter, and * means the preceding atom repeats zero or more times. A parenthesized group is a string of letters or ., with no nesting and no ; a group is always followed by , and an empty group () is allowed. The . in each repetition matches independently. Based on the formal rules and the examples a(b.d) and ab(e.r)e, this site corrects an isolated wrong note in the source: (.) can match ac, and, bcd, and also the empty string.

输入格式

The first line contains the regex, the second line the number of queries q, followed by q lines of queries. An empty query is written as a lone - (- is not a regex character). The source had no numeric bounds; this site uses regex length 1..200, 1≤q≤200, each query length 0..20000, and total query length ≤20000. The regex syntax is guaranteed to be valid, and * only follows an atom and never appears twice in a row.

输出格式

For each query, output YES or NO on its own line.

样例 1

输入：

ab(e.r)*e
2
abbeere
abefretre

输出：

NO
YES

样例 2

输入：

..()*e*
3
code
abeee
cd

输出：

NO
YES
YES

样例 3

输入：

(.)*
4
ac
and
bcd
-

输出：

YES
YES
YES
YES

样例说明

The outputs are NO/YES; NO/YES/YES; YES/YES/YES/YES. An empty ()* consumes no characters and must not loop forever.