Longest Palindrome from Reordered Characters

You are given a string word consisting of lowercase letters. Your task is to rearrange its characters to form the longest possible palindrome. A palindrome is a string that reads the same forwards and backwards.

If it is impossible to form any palindrome from the given characters, output -1.

For example, given the string "aabb", one possible rearrangement producing a palindrome is "abba".

Note: The solution should output the lexicographically smallest valid palindrome when more than one answer exists. The approach is based on the observation that a palindrome can be built using a half formed by sorted characters; if a character appears an odd number of times, it may be used in the center. Mathematically, if the frequency count of a character is cnt, then the number of characters in one half is \(\lfloor \frac{cnt}{2} \rfloor\).

inputFormat

The input consists of a single line containing the string word from standard input (stdin).

The string contains only lowercase letters.

outputFormat

Output a single line to standard output (stdout) containing the longest palindrome that can be formed by rearranging the characters of the input string. If no palindrome can be formed, output -1.

civic

civic