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