Rearrange String to Avoid Adjacent Duplicates

Given a string (s), rearrange the characters of (s) such that no two adjacent characters are the same. If it is possible to rearrange (s) so that it satisfies this condition, output any one valid rearrangement; otherwise, output an empty string "".

A necessary condition for a valid rearrangement is that the frequency (f) of any character must not exceed (\lfloor \frac{n+1}{2} \rfloor), where (n) is the length of the string.

For example, if (s = \texttt{"aabbcc"}), one possible valid rearrangement is (\texttt{"abcabc"}).

inputFormat

The input consists of a single line containing the string (s) (which may be empty).

outputFormat

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

aabbcc

abcabc