Reorganize String

Given a string \(s\), rearrange its characters so that no two adjacent characters are the same. If such a rearrangement is possible, output one valid reorganized string; otherwise, output an empty string.

For example, for \(s = \texttt{aab}\), one possible answer is \(\texttt{aba}\). However, if \(s = \texttt{aaab}\), no valid rearrangement exists and you should output an empty string.

Note: The solution must read the input from standard input (stdin) and print the output to standard output (stdout).

inputFormat

A single line containing the string (s).

outputFormat

Output the reorganized string such that no two adjacent characters are the same. If such an arrangement is not possible, output an empty string.## sample

aab

aba