题目描述

In computing, regular expressions is a powerful tool for text search and string matching. In this problem a simplified version of regular expressions is used:

• An empty string is a regular expression, only the empty string matches it.

• A single lowercase letter c is a regular expression, a string consisting of a single letter $c$ matches it.

• A dot . is a regular expression, a string consisting of any single 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, $x$ matches $α$ and $y$ matches $β$.

• Kleene star: if $α$ is regular expression then (α∗) is a regular expression, a string $s$ matches it only if $s$ is empty or $s =$ xy, $x$ is nonempty and matches $α$ and $y$ matches $(α∗).$ In other words, $s$ consists of zero or more strings, each of them matches $α.$

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

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

Your task is to find the shortest string that matches the given regular expression $E$ and contains the given substring $S$ .

输入格式

The first line of the input file contains the regular expression $E$ . The second line of the input file contains the substring $S (1 \le |E| , |S| \le 10 000)$ .

String $S$ consists of lowercase English letters. Expression $E$ consists of lowercase English letters and special characters: dots (.), parentheses (() and ()), pipes (|), and asterisks (*).

输出格式

Output the shortest possible string $T$ that both matches $E$ and contains $S$ as substring. If there are no such strings, output NO.

The string $T$ should contain only lowercase English letters.

a.*b
bab

abab

(ab)*
bb

NO

提示

Time limit: 10 s, Memory limit: 256 MB.