Rearrange String to Avoid Adjacent Duplicates

You are given a string S consisting of lowercase letters. Your task is to determine if it is possible to rearrange the characters of S such that no two adjacent characters are the same. If such a rearrangement exists, output any one valid rearrangement; otherwise, output an empty string.

A necessary condition for a valid rearrangement is that for every character, its frequency does not exceed \( \lceil \frac{n}{2} \rceil \) where \(n\) is the length of S.

Example:

• Input: aabb
• Output: abab
• Input: aaab
• Output: "" (empty string)

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

inputFormat

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

For example:

aabb

outputFormat

Output a single line containing the rearranged string if a valid rearrangement exists, otherwise output an empty string.

## sample

aabb

abab