Rearrange String to Avoid Consecutive Repeating Characters

Given a string \( s \) consisting of lowercase English letters, rearrange the characters so that no two adjacent characters are the same. If such a rearrangement is impossible, output IMPOSSIBLE.

The rearrangement must satisfy the condition that for every index \( i \) (\( 1 \leq i < |s| \)), \( s_i \neq s_{i+1} \). Use a greedy approach with a max-heap (or an appropriate data structure) to select the best candidate at each step.

Note: If multiple valid answers exist, output the one produced by the defined algorithm.

inputFormat

The input consists of a single line containing the string \( s \) (\(1 \leq |s| \leq 10^5\)), made up exclusively of lowercase English letters.

Input is provided via standard input (stdin).

outputFormat

Output the rearranged string such that no two adjacent characters are identical. If no valid rearrangement exists, output IMPOSSIBLE.

The output should be sent to standard output (stdout).

aaabb

ababa