Rearrange String to Form a Palindrome

Given a string s consisting of lowercase English letters, your task is to rearrange its characters to form a palindrome if possible. A palindrome is defined as a string that reads the same forward and backward. If it is impossible to form any palindrome, output "-1".

Approach: Count the frequency of each character. A necessary and sufficient condition for a valid rearrangement is that at most one character appears an odd number of times. Form the first half of the palindrome by taking half of the count (in sorted order) from each character, designate the middle character (if any), and then mirror the first half.

Mathematical Formulation: A palindrome exists if and only if \( \sum_{i=1}^{k} [f_i \bmod 2] \le 1 \), where \( f_i \) is the frequency of the \(i\)-th distinct letter.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output a single line containing the rearranged palindromic string if possible. If it is impossible to form a palindrome, output "-1".

## sample

aabb

abba

</p>