Reorganize String

You are given a string s consisting only of lowercase English letters. Your task is to rearrange the characters of s to form a new string such that no two adjacent characters are the same.

If it is impossible to construct such a string, output an empty string.

A necessary and sufficient condition for the existence of a valid rearrangement is that for every character the frequency does not exceed \( \lceil \frac{n}{2} \rceil \) where \(n\) is the length of the string.

Note: In case of multiple answers, you must output the lexicographically smallest valid rearrangement.

inputFormat

The input is given via standard input and consists of a single line containing the string s.

outputFormat

Output the lexicographically smallest rearranged string that satisfies the condition. If no valid rearrangement exists, output an empty string.

aab

aba