Rearrange String

Given a string \( s \), rearrange its characters so that no two adjacent characters are the same. If it is impossible to achieve such a rearrangement, output an empty string.

The problem can be solved by using a greedy algorithm with a max-heap to always select the character with the highest remaining frequency, while ensuring that no identical characters come consecutively.

You are required to read the input from standard input (stdin) and print the output to standard output (stdout).

inputFormat

The input consists of a single line containing the string \( s \). The string may contain any characters.

outputFormat

Output a rearranged string such that no two adjacent characters are the same. If no valid rearrangement exists, output an empty string.

aab

aba