Rearrange String to Avoid Adjacent Duplicates

Given a string (s), rearrange its characters so that no two adjacent characters are identical. If such an arrangement is not possible, return an empty string.

For example, if (s = \texttt{aab}), one possible valid rearrangement is (\texttt{aba}). However, if (s = \texttt{aaab}), it is impossible to rearrange the string to meet the criteria, so the answer should be an empty string.

inputFormat

The input consists of a single line containing the string (s) which may include only lowercase English letters. The string length can be up to several hundreds of characters.

outputFormat

Output a single line containing the rearranged string. If it is not possible to rearrange (s) so that no two adjacent characters are the same, output an empty string.## sample

aab

aba