Rearrange String

Given a string \( s \), rearrange its characters so that no two adjacent characters are the same. Formally, for the rearranged string \( t \) of length \( n \), it must satisfy \( t_i \neq t_{i+1} \) for all \( 1 \le i < n \). If no valid rearrangement exists, output an empty string.

The input string contains only lowercase English letters.

inputFormat

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

outputFormat

Output a rearranged string such that no two adjacent characters are the same. If it is impossible to form such a string, output an empty string.## sample

aabb

abab