Rearrange String

Given a string \(s\) consisting of lowercase letters, rearrange the characters so that no two adjacent characters are the same. If such an arrangement is impossible, output an empty string.

For example, if \(s = "aabb"\), one valid output is "abab". Otherwise, if no valid arrangement exists, output an empty string.

inputFormat

The input consists of a single line containing the string (s). This string is read from standard input.

outputFormat

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

aabb

abab