Balanced String Shuffle

You are given a string s consisting only of the characters 'a' and 'b'. Your task is to rearrange the characters of s so that no two consecutive characters are the same. If such a rearrangement is not possible, output Not Possible.

If multiple valid rearrangements exist, output any one of them.

In mathematical terms, if we let n_a be the number of 'a''s and n_b be the number of 'b''s, a necessary condition for a valid rearrangement is that \[ |n_a - n_b| \leq 1 \]

inputFormat

The input is read from standard input (stdin) as a single line containing the string s composed solely of the characters 'a' and 'b'.

outputFormat

Output to standard output (stdout) a rearranged version of the string such that no two adjacent characters are the same. If no valid rearrangement exists, output exactly "Not Possible".## sample

aabb

abab