Rearrange String

Given a string, rearrange it so that no two adjacent characters are the same. If no such rearrangement is possible, output Not possible.

You are required to design a solution that examines the frequency of each character and, if a valid rearrangement exists, distributes the characters to ensure that every adjacent pair is distinct. The problem tests your ability to carefully manage character frequencies and use greedy algorithms.

inputFormat

The input consists of a single line containing a non-empty string to be rearranged.

outputFormat

Output one line: the rearranged string with no two adjacent characters being the same, or Not possible if such an arrangement cannot be achieved.## sample

aabb

abab