Rearrange String to Avoid Adjacent Duplicates

Given a string \( s \) consisting of lowercase English letters, rearrange the characters of \( s \) such that no two adjacent characters are the same. If it is impossible to form such a string, output "Impossible".

Note: A valid rearrangement exists only if for every character \( c \) in \( s \), the frequency \( f(c) \) satisfies \[ f(c) \leq \left\lceil \frac{n}{2} \right\rceil, \] where \( n \) is the length of \( s \). For example, for the string "aab", one valid rearrangement is "aba"; however, for the string "aaab", a valid rearrangement is not possible.

Examples:

• Input: aab → Output: aba
• Input: aaab → Output: Impossible

inputFormat

The input consists of a single line containing a string \( s \) composed of lowercase English letters (a - z). Read the input from standard input.

outputFormat

Print a rearranged string to standard output such that no two adjacent characters are the same. If no such rearrangement exists, print Impossible.

aab

aba