Мінімізація шаблону#508
Для пошуку слів, що складаються з латинських літер у словнику, використовується шаблон, де '?' означає рівно один довільний символ, а '*' — нуль або більше довільних символів. Деякі шаблони вважаються еквівалентними, якщо вони підходять для однакової множини слів. Наприклад, шаблони "*??*a" та "?*?a" підходять для слів з трьох і більше літер, що закінчуються на літеру 'a', але другий шаблон коротший.
Напишіть програму, яка знаходить найкоротший шаблон, еквівалентний до даного.
У вхідному файлі задано кілька шаблонів довжиною від до , що складаються з латинських літер та символів '?' і '*'. Кожен шаблон задано в окремому рядку.
Для кожного шаблону виведіть на відповідному рядку його мінімально еквівалентний шаблон. Якщо є кілька варіантів, виведіть перший у лексикографічному порядку ('*' йде перед '?' за алфавітом).
Приклад 1