Lexicographically Smallest Palindrome

Given a string \(S\) consisting of lowercase English letters, your task is to create the lexicographically smallest palindrome by reordering its characters. A palindrome is a string that reads the same backward as forward. If it is impossible to rearrange all characters of \(S\) into a palindrome, output an empty string.

Note: A string \(P\) is considered lexicographically smaller than string \(Q\) if at the first position where \(P\) and \(Q\) differ, the character in \(P\) comes before the character in \(Q\) in the alphabet.

For example, if \(S = \texttt{aabbcc}\), one possible palindrome is \(\texttt{abccba}\) which is the lexicographically smallest palindrome that can be formed using all characters.

inputFormat

The input consists of a single line containing a string \(S\) made up of lowercase English letters. The length of \(S\) can be up to \(10^6\) characters.

outputFormat

Output the lexicographically smallest palindrome that can be formed by reordering all the characters of \(S\). If it is impossible to form such a palindrome, output an empty string.

aabbcc

abccba