Rearrange String without Adjacent Duplicates

Given a string \(s\), rearrange its characters so that no two adjacent characters are the same. If such a rearrangement is impossible, output an empty string.

The solution should read the input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input consists of a single line containing a string \(s\) composed of lowercase English letters.

outputFormat

Output a rearranged string where no two adjacent characters are identical. If no valid rearrangement exists, output an empty string.

aab

aba