Rearrange Palindrome

Given a string s containing only lowercase English letters, your task is to rearrange its characters to form a palindrome if possible. A palindrome is a string that reads the same forwards and backwards.

A necessary and sufficient condition for a string to be rearranged into a palindrome is that at most one character can have an odd frequency. In other words, if we denote the frequency of character \(c_i\) by \(n_i\), then at most one \(c_i\) can satisfy \(n_i \mod 2 \neq 0\). If a palindrome can be formed, output one valid rearrangement; otherwise, output an empty string.

inputFormat

The input consists of a single line containing a non-empty string s composed of lowercase English letters.

outputFormat

Output a single line containing the palindrome formed by rearranging the characters of s if possible. If no palindrome can be formed, output an empty string.

aabb

abba