Rearrange String

Given a string (S), rearrange its characters so that no two adjacent characters are identical. Formally, find a permutation (S') of (S) such that for every valid index (i), (S'i \neq S'{i+1}). If such a rearrangement is possible, output one valid arrangement; otherwise, print "Not Possible". The input string will consist of only printable characters and its length is at least 1. This problem tests your understanding of greedy algorithms and priority queues.

inputFormat

The input is provided via standard input (stdin) as a single line containing the string (S).

outputFormat

Output a single line to standard output (stdout) containing a rearranged string where no two adjacent characters are the same. If no such rearrangement is possible, output "Not Possible".## sample

a

a