Reformat String

Given a string (s) of length (n), rearrange its characters so that no two adjacent characters are identical. A valid reformatting exists if for every character (c), its frequency (f(c)) satisfies

[ f(c) \leq \lceil \frac{n}{2} \rceil ]

If it is impossible to reformat the string, output "Not Possible".

For example:

• Input: aab → Output: aba
• Input: aaab → Output: Not Possible

Try to design an efficient algorithm that works well even if (n) is large.

inputFormat

The input is given via standard input (stdin) as a single line containing the string (s) which consists only of lowercase English letters.

outputFormat

The output is produced on standard output (stdout) as a single line. It should be a rearranged string where no two adjacent characters are identical, or the string "Not Possible" if such a rearrangement cannot be achieved.## sample

aab

aba