Rearrange String

Given a string s, your task is to rearrange its characters so that no two adjacent characters are the same. If such an arrangement is not possible, output Not possible.

The input string consists of lowercase alphabets only. Note that there may be multiple valid answers; however, you are required to output the string as determined by the algorithm described below.

The algorithm uses a greedy approach based on a max-heap (priority queue) to always select the character with the highest remaining frequency that is not equal to the previously placed character. Formally, let f(c) denote the frequency of character c in s. The algorithm repeatedly selects a character c with the maximum f(c) subject to c not being equal to the last appended character, appends c to the result, and decrements f(c) by one. If at any point no valid character can be selected, the answer is declared "Not possible".

inputFormat

The input is read from standard input (stdin) as a single line containing the string s.

outputFormat

Print to standard output (stdout) a rearranged string such that no two adjacent characters are the same. If no valid rearrangement exists, print "Not possible".## sample

aaabbc

ababac