Районно-городские командные соревнования

Для поиска слов, состоящих из латинских букв, в некотором словаре используется шаблон, в котором '?' означает ровно один произвольный символ, а '*' – ноль или более произвольных символов. Некоторые шаблоны являются эквивалентными, то есть соответствуют одинаковому множеству слов. Например, оба шаблона "*??*a" и "?*?a" соответствуют словам из трех или более букв, оканчивающимся на букву 'a', но второй шаблон короче.

Напишите программу, которая находит самый короткий шаблон, эквивалентный заданному.

Входной файл содержит несколько шаблонов длиной от 1 до 50 символов, состоящих из латинских букв и символов '?' и '*'. Каждый шаблон записан на отдельной строке.

В выходной файл для каждого шаблона вывести на соответствующей строке его минимальный эквивалент. Если существует несколько вариантов, вывести первый в лексикографическом порядке ('*' идет в алфавите раньше '?')

*??*a
T***nd?*
*?*?*?*

*??a
T*nd*?
*???