Rearrange String to Avoid Adjacent Duplicates

Given a string S, rearrange the characters such that no two adjacent characters are the same. If such an arrangement is possible, output the rearranged string; otherwise, output (\text{Not possible}).

The solution should employ a greedy algorithm using a priority queue (heap) to choose the character with the highest remaining frequency while ensuring that no two identical characters are adjacent. In the event of multiple valid answers, the implementation should follow a deterministic approach based on lexicographical order.

inputFormat

The input consists of a single line containing the string (S) of lowercase letters only.

outputFormat

Output a rearranged string where no two adjacent characters are the same. If no valid arrangement exists, output (\text{Not possible}).## sample

aabb

abab