Problem C. Regular Expression

Time limit: 20 seconds

Problem

Regular expressions are widely used as a means of finding string patterns. It is often used in writing programs. Regular expressions are supported by many languages such as Java, Perl and Python.

Each regular expression represents a set of strings.
In this problem, a regular expression may be formed by:

  1. An empty string - represents the set containing the empty string only, i.e., {Ø}
  2. A lowercase or uppercase letter a - z or A - Z - any letter represents the set containing the letter itself only
  3. [<re1>|<re2>|...|<ren>]), where n >= 1 - represents the set <re1> ∪ <re2> ∪ ... ∪ <ren>
  4. <re1><re2><re3>...<ren> - represents the set of string such that each string can be formed by concatenating a string represented by <re1>, a string represented by <re2> ... a string represented by <ren>
  5. (<re>) - represents the set of {Ø} ∪ <re> ∪ <re><re> ∪ <re><re><re> ∪ ...
Your task is to answer whether a query string belongs to a given regular expression.

Input

Each pair of lines in the input represents a test case.The first line of the each test case is a regular expression. The second line is the query. The maximum lengths of both the regular expression and the query are 1000.

Output

For each test case, print "Yes" if the query string belongs to the regular expression. Print "No" otherwise.

Sample Input

a(b)[c|d]
abc

Sample output

Yes

Author

Louis Siu