406559: GYM102441 A Template for Search

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Template for Searchtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

First line contains a string $$$s$$$ — a template string. This string contains only lower case latin letters, symbols '?' and '*'.

$$$$$$ 1 \le |s| \le 500$$$$$$

Output

You 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?ba
Output
abacaba
Input
ac?ba
Output
-1

加入题单

上一题 下一题 算法标签: