# HackerEarth - Shil, and Palindrome Solution

Shil is your new boss and he likes palindromes very much. Palindrome is a string that can be read the same way in either direction, from the left to the right and from the right to the left. (ex. madam , aabaa, racecar)

Given a string **S** , beautiful Palindrome is a lexicographical minimum palindrome that can be formed by rearranging all the characters of string **S**. In order to please your boss, find a beautiful Palindrome that can be formed with help of string **S**.

String **x** is lexicographically less than string **y**, if either **x** is a prefix of **y** (and **x** ≠ **y**), or there exists such **i** (1 ≤ **i** ≤ min(**|x|, |y|)**), that **x _{i} < y_{i}**, and for any

**j**(1 ≤

**j**<

**i**)

**x**. Here

_{j}= y_{j}**|a|**denotes the length of the string

**a**. The lexicographic comparison of strings is implemented by operator < in modern programming languages.

**Input:**

Only line of input contains string **S**. All the letters of this string will be in lower letters(**'a' - 'z'**).

**Output:**

Output lexicographical minimum Palindrome that can be formed by rearranging all the letters of string **S**. If no such Palindrome exist for given input, print **-1**.

**Constraints:**

1≤|S|≤100000

SAMPLE INPUT

`aabcc `

SAMPLE OUTPUT

`acbca `

Explanation

After rearranging all the characters , all the palindromes that can be formed are cabac and acbca. Out of these two lexicographical minimum one is acbca.

### Solution in Python

```
import sys
from collections import Counter
s = input().strip()
c = Counter(s)
pal = ""
mid = ""
odd = 0
for k,v in c.items():
if v%2:
odd+=1
mid+=k
v-=1
pal+=k*(v//2)
if odd > 1 :
print("-1")
else:
pal = "".join(sorted(pal))
print(pal+mid+pal[::-1])
```