Reorganize String to Avoid Adjacent Duplicates

Given a string s, rearrange its characters so that no two adjacent characters are the same. If it is impossible to rearrange s in such a way, output an empty string.

This can be thought of mathematically as follows: Given a string \( s \) of length \( N \), find a permutation \( \pi \) of \( \{0, 1, 2, \dots, N-1\} \) such that for every index \( i \) (where \( 0 \le i < N-1 \)), \( s[\pi(i)] \neq s[\pi(i+1)] \).

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output a single line: the rearranged string that satisfies the condition. If no valid rearrangement exists, output an empty string.

aab

aba