Rearrange String into Palindrome

You are given a string s consisting of lowercase letters. Your task is to rearrange the characters of s to form a palindrome. A palindrome is a string that reads the same forwards and backwards.

If it is possible to rearrange the string into a palindrome, output one valid palindrome arrangement. If it is not possible, output IMPOSSIBLE.

Recall that a string can be rearranged into a palindrome if and only if at most one character appears an odd number of times. In mathematical terms, for a counter \( C \) of characters, the condition is:

[ \sum_{c} \mathbf{1}_{{C(c) \ % \ 2 \neq 0}} \leq 1 ]

Example:

• Input: aabb → Output: abba (or baab)
• Input: abc → Output: IMPOSSIBLE
• Input: aabbc → Output: abcba

inputFormat

The input consists of a single line containing a string s composed of lowercase letters.

outputFormat

If a palindrome rearrangement exists, output one valid palindrome. Otherwise, output IMPOSSIBLE.

aabb

abba