Make a Palindrome

Interview

Time limit2sMemory limit128 MB

Summary

Rearrange the letters of a given uppercase string into the lexicographically smallest palindrome, or report it is impossible.

Level: Medium4 of 10
Topics: String, Greedy, Sorting
Solved: No attempts yet

Problem

Given a name written with uppercase English letters, rearrange all of its letters to make a palindrome.

If more than one palindrome can be made, output the lexicographically smallest one. If no palindrome can be made, output the required impossible string.

Input

The first line contains the name. It consists only of uppercase English letters and has length at most 50.

Output

Output the answer on one line. If it is impossible to rearrange the letters into a palindrome, output I'm Sorry Hansoo.

Examples4

Example 1
Input
```
AABB
```
Expected output
```
ABBA
```
Example 2
Input
```
AAABB
```
Expected output
```
ABABA
```
Example 3
Input
```
ABACABA
```
Expected output
```
AABCBAA
```
Example 4
Input
```
ABCD
```
Expected output
```
I'm Sorry Hansoo
```