Anti-Palindrome

Time limit2sMemory limit128 MB

Summary

Rearrange all characters of a string to form the lexicographically smallest anti-palindrome, where each pair of symmetric positions must differ, or report impossible.

Level: Medium6 of 10
Topics: Greedy, String, Combinatorics, Backtracking
Solved: No attempts yet

Problem

Let n be the length of a string P. The string P is an anti-palindrome if, for every integer i with 0 <= i < floor(n/2), the characters P[i] and P[n-i-1] are different. If the length is odd, the middle character may be anything.

For instance, "c", "cpp", and "java" are anti-palindromes, while "test", "pp", and "weather" are not.

You are given a string S. Rearrange all characters of S exactly once to form an anti-palindrome. If there are multiple valid rearrangements, print the lexicographically smallest one.

Input

The first line contains the string S. Its length is at most 50, and it consists only of lowercase English letters.

Output

Print the lexicographically smallest rearrangement that satisfies the condition. If no such rearrangement exists, print -1.

Examples5

Example 1
Input
```
hello
```
Expected output
```
ehllo
```
Example 2
Input
```
test
```
Expected output
```
estt
```
Example 3
Input
```
aabbcc
```
Expected output
```
aabcbc
```

Example 4

Input

reflectionnoitcelfer

Expected output

cceeeeffiillnnoorrtt

Example 5
Input
```
www
```
Expected output
```
-1
```