Rearrange String

Given a non-empty string s, rearrange its characters so that no two adjacent characters are the same. If such a reordering exists, output one valid rearrangement; otherwise, output an empty string.

The solution should read input from stdin and write the answer to stdout.

The problem can be formally stated as follows:

Given a string \( s \) of length \( n \), rearrange the characters of \( s \) to form a new string \( t \) such that for every \( 1 \le i < n \), \( t_i \neq t_{i+1} \). If no such rearrangement exists, return an empty string.

inputFormat

A single line containing the string ( s ).

outputFormat

A single line containing the rearranged string if possible; otherwise, an empty string.## sample

aab

aba