Orange Boy(Monk.eyk.ing),Red girl(Mack.erel.pike) and their cat LGM(Legendary.Grand.Meow) are a happy family. But in fact, they are the heroes that is helping the world in silent.
One day, the earth is under the attack by the Implementation Dragon. So the three went off to divide and conquer.

The three must fight together to solve the OI question by the I.D.(Implementation Dragon)

As we know, a Regex is a kind of pattern to match strings. The pattern can be seen as many subpatterns. In this problem, we will consider a easy problem.

Patterns could be:

1. "a" - any lower-case letter. This will match the exactly character. For example, Regex "a" will only match string "a"

2. "a|b" - match a or b. For example, Regex "y|p" will match "y" or "p"

3. "[abc]" - match exactly one in the bracket. eg. "[abc]" will match "a" or "b" or "c"

4. "." - a dot will match any character. eg."." will match "a" "b" "c"... "z"

5. "a" - may match 0 or more times. eg. "a" will match ""(empty string) "a" "aa" "aaa" ... "aaaaaa" etc

6. "()" - to make things altogether. eg."(abc)|(def)" will match "abc" or "def"

All together, for example, "https*" will match "http" "https" "httpss" ... etc

"([abc]*)|y|p" will match any string consisted only of abc and "y" and "p".

Now you are going to help one hero.

# Helping LGM

You are given a Regex pattern. Your task is to find out if it is a valid pattern.

# Helping Orange Boy

You are given a Regex pattern. Your task is to find out any string that matches this pattern.

"([abc]*)|y|p" Output:"abc"

# Helping Red Girl

You are given a Regex pattern and a string. Your task is to find out whether the string matches the pattern.

"([abc]*)|y|p" and "y" answer is YES
"x" and "y" answer is NO

# Constriants

The string consists of only lower-case letters and necessary special characters. The length does not exceed 50.

# Solution By XGN

Problem is too easy to give out my answer. Use Python and Java will be useful.