Rearrange Characters in a String

Given a string s, rearrange the characters so that no two adjacent characters are the same. If it is impossible to rearrange, output an empty string.

For example, if s = "aabb", valid outputs include "abab" or "baba". Your solution must read the input from standard input and output the result to standard output.

The underlying idea is to use a greedy approach with a max-heap (or priority queue) to always pick the character with the highest remaining frequency, ensuring that no two adjacent characters are the same.

inputFormat

The input consists of a single line containing the string s. The string may include lowercase and uppercase letters, and its length may be zero.

outputFormat

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

## sample

aabb

abab

</p>