시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 256 MB32266.667%

문제

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 ≤ |E| , |S| ≤ 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.

예제 입력 1

a.*b
bab

예제 출력 1

abab

예제 입력 2

(ab)*
bb

예제 출력 2

NO