Rearrange String to Avoid Adjacent Duplicates

You are given a string s consisting of lowercase English letters. Your task is to rearrange the characters of s such that no two adjacent characters are the same. If it is not possible to rearrange the string as required, output an empty string.

More formally, let the rearranged string be t. Then for every index i with 1 ≤ i < |t|, t[i] ≠ t[i+1] must hold. It can be shown that a valid rearrangement exists if and only if \[ \max_{c \in \{a, \ldots, z\}} f(c) \leq \left\lceil \frac{|s|}{2} \right\rceil, \] where \(f(c)\) denotes the frequency of character \(c\) in string s.

If multiple answers are possible, output any one of them.

inputFormat

The input is read from stdin and consists of a single line containing the string s (0 ≤ |s| ≤ 10⁵), which only contains lowercase English letters.

outputFormat

Print the rearranged string to stdout. If no valid rearrangement exists, print an empty string.

## sample

aab

aba

</p>