Problems
Minimization template
Minimization template
Для поиска слов, состоящих из латинских букв, в некотором словаре используется шаблон, в котором '\textbf{?}' означает ровно один произвольный символ, а '\textbf{*}' -- ноль или более произвольных символов. Некоторые шаблоны являются эквивалентными, то есть соответствуют одинаковому множеству слов. Например, оба шаблона "\textbf{*??*a}" и "\textbf{?*?a}" соответствуют словам из трех или более букв, оканчивающимся на букву '\textbf{a}', но второй шаблон короче.
Напишите программу, которая находит самый короткий шаблон, эквивалентный заданному.
\InputFile
Входной файл содержит несколько шаблонов длиной от \textbf{1} до \textbf{50} символов, состоящих из латинских букв и символов '\textbf{?}' и '\textbf{*}'. Каждый шаблон записан на отдельной строке.
\OutputFile
В выходной файл для каждого шаблона вывести на соответствующей строке его минимальный эквивалент. Если существует несколько вариантов, вывести первый в лексикографическом порядке ('\textbf{*}' идет в алфавите раньше '\textbf{?}')
Input example #1
*??*a T***nd?* *?*?*?*
Output example #1
*??a T*nd*? *???