Rearrange String to Avoid Adjacent Duplicates

You are given a string s consisting of letters and/or digits. Your task is to rearrange its characters such that no two adjacent characters are identical. If it is impossible to produce such an ordering, output Not Possible.

The problem can be formalized as follows. Given a string \( s \) of length \( n \), rearrange \( s \) into a string \( t \) satisfying: \[ \forall i \in \{1,2,\ldots,n-1\},\quad t_i \neq t_{i+1} \] If no such permutation exists, print Not Possible.

Note: In cases where multiple rearrangements exist, any valid rearrangement is acceptable.

inputFormat

The input is provided via standard input and consists of a single line containing the string s.

outputFormat

Output a single line: a rearranged string where no two adjacent characters are identical. If such a rearrangement is not possible, output Not Possible.

aabb

abab