Reorganize String

You are given a string s. Rearrange the characters of the string so that no two adjacent characters are identical. If it is impossible to do so, output an empty string.

One useful observation is that if any character appears more than $\lceil\frac{n}{2}\rceil$ times (where \(n\) is the length of the string), then it is impossible to reorganize the string, and you should output an empty string.

For example, given the string "aab", one possible valid reorganization is "aba". However, if the input is "aaab", then no valid reorganization exists, so the output should be an empty string.

inputFormat

The input consists of a single line containing the string s (with at least one character).

outputFormat

Output a reorganized string that satisfies the condition: no two adjacent characters are the same. If no valid reorganization exists, output an empty string.

aab

aba