Template for Search

시간 제한1초메모리 제한256 MB

요약

물음표는 임의의 한 글자, 별표는 임의 길이의 문자열에 대응하는 패턴에 맞는 가장 짧은 회문을 찾는다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 문자열, 그리디
정답자: 아직 제출이 없습니다

문제

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.

입력

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

출력

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.

제한

$1 \le |s| \le 500$

예제2

예제 1
입력
```
*ac?ba
```
예상 출력
```
abacaba
```
예제 2
입력
```
ac?ba
```
예상 출력
```
-1
```