406559: GYM102441 A Template for Search
Description
You are required to find a palindome string with a minimal length which matches a given template for search. Palindrome is a string which can be read in the same way in both directions (forward and backward). An empty string is also a palindrome. The template can contain lower case latin letters corresponding to the same letters in a string, symbol '?' corresponding to an arbitrary latin letter and symbol '*' corresponding to a zero or more arbitrary latin letters.
InputFirst line contains a string $$$s$$$ — a template string. This string contains only lower case latin letters, symbols '?' and '*'.
$$$$$$ 1 \le |s| \le 500$$$$$$
OutputYou are required to print a single line containing a palindrome string with a minimal length which matches a given template. The palindrome should contain only lower case latin letters. If there is no such palindrome, you are required to output "-1". If there are multiple possible palindromes, you may output any of them.
ExamplesInput*ac?baOutput
abacabaInput
ac?baOutput
-1