Reorganize String

You are given a string S consisting of lowercase English letters. Your task is to rearrange the characters of the string such that no two adjacent characters are the same. If such a rearrangement is possible, output the rearranged string; otherwise, output an empty string.

The solution should strive to distribute the characters as evenly as possible. For example, if S = aabb, one possible valid answer is abab (another valid answer is baba, but your program should deterministically output one valid answer following the algorithm described below).

Note: If multiple rearrangements exist, the algorithm described in the solutions will always produce the same output given the same input.

Constraints:

• Let \( n = |S| \). You may assume \( 0 \le n \le 10^5 \).

The algorithm used in the provided solutions is similar to the greedy approach using a max-heap. In \( \LaTeX \) style, the key idea can be written as:

[ \text{while } \text{heap} \neq \emptyset:\quad \text{pop the element } (c, f) \text{ with maximum frequency } f \ \text{append } c \text{ to the result, and update } f := f-1, \text{ ensuring that the same character is not used consecutively.} ]

inputFormat

The input is read from standard input (stdin) and consists of a single line containing the string S.

outputFormat

Output to standard output (stdout) a single line containing the rearranged string if a valid rearrangement exists, or an empty string otherwise.

## sample

aabb

abab