Reorganize String

Given a string S, determine whether it is possible to rearrange the characters of S such that no two adjacent characters are identical. If such a reordering exists, output any valid rearrangement. Otherwise, output an empty string.

A necessary and sufficient condition for the existence of a valid reordering is that for every character, its frequency does not exceed \( \left\lfloor \frac{n+1}{2} \right\rfloor \), where \( n \) is the length of the string.

inputFormat

The input consists of a single line containing the string S (1 ≤ |S| ≤ 10⁵). The string consists of printable ASCII characters.

outputFormat

Output a single line. If a valid reordering exists, output one such rearranged string where no two adjacent characters are the same; otherwise, output an empty string.

aab

aba