Rearrange String

You are given a string \(s\) consisting of lowercase English letters. The task is to rearrange the characters of \(s\) such that no two adjacent characters are the same. If it is possible to obtain such a rearrangement, output one valid rearranged string. Otherwise, output an empty string.

The input string is provided on a single line. You must output the rearranged string to standard output. If no valid rearrangement exists, output an empty string.

Note: In case there are multiple valid answers, your program can output any one of them.

inputFormat

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

outputFormat

Output a single line containing the rearranged string such that no two adjacent characters are identical. If it is not possible to rearrange, output an empty string.

## sample

aab

aba

</p>