Reorganize String

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

Note: The solution must be efficient since the input string can be very large. The approach typically involves using a max-heap (or priority queue) to always select the character with the highest remaining frequency, while ensuring that the same character is not placed consecutively.

For example, for an input S = "aab", a possible output is "aba". If no valid rearrangement exists (e.g. S = "aaab"), then output Not possible.

inputFormat

The input is provided via standard input. It consists of a single line containing the string S (only lowercase English letters).

outputFormat

Output via standard output a valid rearranged string such that no two adjacent characters are identical. If no such rearrangement exists, output Not possible.

## sample

aab

aba

</p>