Reorganize String

Given a string \(s\), rearrange its characters so that no two adjacent characters are the same. If such an arrangement is not possible, output an empty string.

For instance, for an input string "aab", one valid output is "aba". However, for "aaab" no valid reorganization exists and the output should be an empty string.

Note that the result must satisfy the condition \(s_i \neq s_{i+1}\) for all valid indices \(i\). In cases where multiple answers are possible, any valid answer is acceptable.

inputFormat

The input is provided via standard input (stdin) and consists of a single line containing the string \(s\) to be reorganized.

outputFormat

Output the reorganized string via standard output (stdout). If no valid reorganization exists, output an empty string.

aab

aba