Template Minimization#508
To search for words consisting of Latin letters in a dictionary, a pattern is used where '?' stands for exactly one arbitrary character, and '*' stands for zero or more arbitrary characters. Some patterns are considered equivalent if they match the same set of words. For example, the patterns "*??*a" and "?*?a" both match words of three or more letters ending with the letter 'a', but the second pattern is shorter.
Write a program that finds the shortest pattern equivalent to the given one.
The input file contains several patterns, each of length from to , consisting of Latin letters and the symbols '?' and '*'. Each pattern is given on a separate line.
For each pattern, output its minimal equivalent on the corresponding line. If there are several options, output the first in lexicographical order ('*' comes before '?' alphabetically).
Example 1