В семье программистов родился ребенок. Папа-программист хочет назвать ребенка так, чтобы его имя подходило под шаблон P, а мама-программист настаивает на шаблоне M. Найдите самое короткое имя, удовлетворяющее обоим шаблонам, или сообщите, что такого имени не существует и семья находится на грани развода.
Шаблон представляет собой последовательность букв русского алфавита (буква «ё» не используется) и специальных символов, которые имеют следующие значения:
? |
любая буква |
* |
любое (возможно нулевое) число букв |
[P] |
любая буква из диапазона P |
[!P] |
любая буква не из диапазона P |
{n} |
предыдущий символ, повторенный ровно n раз |
{n;} |
предыдущий символ, повторенный не менее n раз |
{n;m} |
предыдущий символ, повторенный от n до m раз |
@ |
предыдущий символ, повторенный не менее одного раза |
При этом 0 £ n £ m £ 10. Диапазон задается перечислением через запятую символов и интервалов символов. Интервал символов записывается в виде a-b, что означает любую букву, расположенную в алфавите между a и b включительно.
Символы могут комбинироваться. Например, запись [а,о,е,у,и,ы,э-я]@ означает произвольную непустую последовательность гласных (необязательно повторяющихся). Запрещается записывать подряд фигурные скобки и символы @.
В первой строке входного файла записан шаблон папы, а во второй — шаблон мамы. Длина каждого шаблона не превосходит 80 символов.
Выведите в выходной файла кратчайшее имя ребенка, удовлетворяющее обоим шаблонам, если такое имя существует. Имя ребенка должно состоять из букв русского алфавита. Большие и маленькие буквы не различаются. В случае нескольких возможных имен требуется вывести первое по алфавиту. Если искомого имени не существует, выведите сообщение «NO SOLUTION».
?ик*т[а-о][л-р]*
В??тор*
Виктор