Rearrange String

You are given a string s. Rearrange the characters of s so that no two adjacent characters are identical. If there exists at least one valid rearrangement, output any one of them; otherwise, output IMPOSSIBLE.

Note: A rearrangement is valid if for every two consecutive characters in the output string, they are not equal. Formally, for the output string t, it must be that t[i] ≠ t[i+1] for all i (1 ≤ i < |s|).

Input and output are to be managed via standard input and standard output respectively.

inputFormat

The input consists of a single line containing the string s (1 ≤ |s| ≤ 10⁵), composed of lowercase and/or uppercase English letters.

outputFormat

Output a rearranged string where no two adjacent characters are the same. If no valid rearrangement exists, output IMPOSSIBLE.

aabb

abab