Rearrange String Avoiding Adjacent Duplicates

You are given a string S and your task is to rearrange the characters of S such that no two adjacent characters are the same.

If such an arrangement is possible, output one valid rearranged string. Otherwise, output Not possible.

One can think of the necessary condition as follows: Let \( f_{max} \) be the highest frequency of any character in S. A valid rearrangement exists if and only if \( f_{max} \leq \lceil \frac{n}{2} \rceil \), where \( n \) is the length of the string.

Note: The answer is not necessarily unique. Any valid rearrangement is acceptable.

inputFormat

The input is provided from standard input and consists of a single line that contains the string S.

outputFormat

Output a single line to standard output. If a valid rearrangement exists, output the rearranged string. Otherwise, output Not possible.

aabb

abab