Reorganize String

Given a string s consisting of lowercase English letters, rearrange the characters of s so that no two adjacent characters are the same. If such a rearrangement is impossible, output an empty string.

A necessary and sufficient condition for a valid reorganization is that if n is the length of the string and f_max is the highest frequency of any character, then it must hold that \[ f_{\max} \leq \left\lceil \frac{n}{2} \right\rceil. \]

You are required to read the input from standard input and print the answer to standard output.

inputFormat

The input consists of a single line containing the string s (1 \leq |s| \leq 10^5), which is composed of lowercase English letters only.

outputFormat

Print a single line containing any valid reorganization of s such that no adjacent characters are the same. If no valid rearrangement exists, print an empty string.

aab

aba