Expression and Substring

A regular expression describes a set of strings. This problem uses only the simplified form defined by these rules.

• The empty string is a regular expression. Only the empty string matches it.
• A single lowercase letter c is a regular expression. Only the one letter string c matches it.
• The dot . is a regular expression. Any string of one lowercase letter matches it.
• Alternation: if α and β are regular expressions, then (α|β) is a regular expression. A string s matches it only if s matches α or s matches β.
• Concatenation: if α and β are regular expressions, then (αβ) is a regular expression. A string s matches it only if s = xy, where x matches α and y matches β.
• Kleene star: if α is a regular expression, then (α*) is a regular expression. A string s matches it only if s is empty, or s = xy where x is nonempty and matches α and y matches (α*). In other words, s is a concatenation of zero or more strings that each match α.

Parentheses can be omitted. The Kleene star has the highest priority, concatenation has medium priority, and alternation has the lowest priority. So abc*|de means (ab(c*))|(de).

For example, abcabcab matches a(bc|a)*ab, but abcbab does not.

You are given a regular expression E and a string S. Find the shortest string that matches E and contains S as a substring.

The first line contains the regular expression E. The second line contains the string S ($1 \le |E|, |S| \le 2000$).

S consists of lowercase English letters. E consists of lowercase English letters and the special characters ., (, ), |, *, and E is a valid regular expression under the rules above.

Print the shortest string T that matches E and contains S as a substring. If several strings share that shortest length, print the lexicographically smallest one. If no such string exists, print NO.

T consists of lowercase English letters only.