Longest Palindrome Rearrangement

Given a string S, your task is to determine the longest palindrome that can be formed by rearranging its characters. A palindrome is a string that reads the same forwards and backwards. In order for a palindrome to be constructed from the characters in S, at most one character may occur an odd number of times. Formally, if the frequency of the i^th character is denoted by \(n_i\), then a palindrome can be constructed if:

\(\sum_{i=1}^{k} \mathbb{1}_{(n_i \bmod 2 = 1)} \le 1\)

If this condition is not met, output an empty string.

The palindrome must be constructed as follows: sort the characters in increasing order, for each character append exactly \(\lfloor n_i/2 \rfloor\) copies to the first half, select the character with an odd count (if any) as the middle character, and finally append the reverse of the first half to form the complete palindrome.

inputFormat

The input consists of a single line containing the string S. The string might contain letters, digits, or special characters.

Note: The input is provided via standard input (stdin).

outputFormat

Output the longest palindrome that can be constructed by rearranging the characters of S. If no valid palindrome can be constructed (i.e. if more than one character occurs an odd number of times), output an empty string.

The output should be printed to standard output (stdout).

aabbcc

abccba