Rearrange String to Avoid Adjacent Duplicates

Given a string S, rearrange its characters such that no two adjacent characters are identical. If possible, output the lexicographically smallest valid arrangement; otherwise, output "Not Possible".

A rearrangement is valid if for every two consecutive characters c_i and c_i+1, c_i \(\neq\) c_i+1. It is mathematically necessary that the frequency of any character does not exceed \(\lceil \frac{n}{2} \rceil\), where \(n\) is the length of S.

inputFormat

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

outputFormat

Output a single line that contains the lexicographically smallest rearranged string with no two identical adjacent characters, or "Not Possible" if such an arrangement is not feasible.

aaabb

ababa