Rearrange String for Beauty

You are given a string s composed of lowercase English letters. Your task is to rearrange the characters of s so that no two adjacent characters are the same. If it is possible to rearrange the string in such a way, output any valid rearrangement. Otherwise, output Not Possible.

Hint: A common approach is to count the frequency of each character and use a max-heap (priority queue) to greedily select the character with the highest remaining frequency that is not equal to the previously placed character. The necessary condition for a valid rearrangement is that for the character with maximum frequency, say \(f_{max}\), it must hold that \[ f_{max} \leq \left\lfloor \frac{n+1}{2} \right\rfloor, \] where \(n\) is the total length of the string.

inputFormat

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

outputFormat

Output a single line: a rearranged string where no two adjacent characters are the same, or Not Possible if no valid rearrangement exists.

aab

aba