Выражение
При вычислении регулярные выражения являются мощным инструментом для текстового поиска и сопоставления строк. В этой задаче используется упрощенная версия регулярных выражений:
Пустая строка "" является регулярным выражением, и только пустая строка соответствует ей.
Одна строчная буква "c" является регулярным выражением. Строка, состоящая из одной буквы c, соответствует ему.
Точка "." является регулярным выражением. Строка, состоящая из любой единственной буквы, соответствует ему.
Чередование: если a и b регулярные выражения, то "(a|b)" также регулярное выражение, строка s соответствует ему, если только s соответствует a или b.
Конкатенация: если a и b регулярные выражения, то "(ab)" также регулярное выражение, строка s соответствует ему только если s = xy, x соответствует a и y соответствует b.
Звезда Клини: если a регулярное выражение, то "(a*)" также регулярное выражение, строка s соответствует ему только если s пусто или s = xy, x непусто и соответствует a и y соответствует (a*). Другими словами, s состоит из нуля или более строк, каждая из которых соответствует a.
Скобки можно опустить, в этой задаче звезда Клини имеет наивысший приоритет, конкатенация имеет средний приоритет и чередование имеют самый низкий приоритет. То есть "abc*|de" означает "(ab(c*))|(de)".
Например, строка "abcabcab" соответствует "a(bc|a)*ab", но строка "abcbab" нет.
Вам следует найти кратчайшую строку, которая соответствует данному регулярному выражению E, и содержит заданную подстроку S.
Входные данные
Первая строка содержит регулярное выражение E. Вторая строка содержит подстроку S (1 ≤ |E|,|S| ≤ 10 000).
Строка S состоит из прописных латинских букв. Выражение E состоит из прописных латинских букв и специальных символов: точки ('.'), скобок ('(' и ')'), трубы ('|') и звездочек ('*').
Выходные данные
Выведите кратчайшую строку T, которая соответствует E и содержит S как подстроку. Если такой строки не существует, вывести "No".
Строка T должна содержать только прописные латинские буквы.