Rearrange Letters

You are given a string s consisting of lowercase English letters. Your task is to rearrange the letters of s so that no two adjacent characters are the same. If such an arrangement is not possible, output an empty string.

For example, given the string "aabb", one possible valid rearrangement is "abab". However, if the string is "aaab", no valid rearrangement exists, so the output should be an empty string.

Note: When multiple valid rearrangements exist, your program may output any one of them, but to ensure consistency in grading, the provided solutions follow a deterministic ordering.

inputFormat

A single line containing the string s, which consists of lowercase English letters.

outputFormat

Output a single line containing the rearranged string such that no two adjacent characters are the same. If no valid rearrangement exists, output an empty string.## sample

aabb

abab