Reorganize String

You are given a string s. Your task is to rearrange the characters of the string so that no two adjacent characters are the same. If such a rearrangement is possible, output any one valid reorganized string. Otherwise, output an empty string.

Note: The rearranged string is not necessarily unique, but your solution must produce one valid answer if possible.

Example: For input s = "aab", a valid output is aba while for s = "aaab" the output should be an empty string.

inputFormat

The input consists of a single line containing a non-empty string s.

The string consists of characters which may include letters and/or other symbols.

outputFormat

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

aab

aba