Rearranging Strings to Avoid Adjacent Duplicates

Given a string s consisting of lowercase alphabets, determine whether it is possible to rearrange the characters so that no two adjacent characters are the same. If such a rearrangement is possible, output one valid rearrangement; otherwise, output Not possible.

Note: A valid rearrangement exists if and only if for the input string of length \(n\), every character \(c\) satisfies \[ \text{count}(c) \le \frac{n+1}{2}. \]

For example, given s = "aaabb", one possible valid output is ababa, whereas for s = "aaab" it is impossible to rearrange to meet the condition.

inputFormat

A single line containing a string s composed of lowercase alphabets.

outputFormat

A single line containing a valid rearrangement of s where no two adjacent characters are the same, or the string "Not possible" if no valid rearrangement exists.## sample

aaabb

ababa