Rearrange to Palindrome

You are given a string s consisting of lowercase letters. Your task is to determine whether it is possible to rearrange the characters of the string so that the resulting string is a palindrome.

A palindrome is a string that reads the same backwards as forwards. If it is possible, you must print one possible palindrome that can be constructed using all the characters of the input string. If it is not possible, print Not possible.

The solution involves counting the frequency of each character. In a palindrome, at most one character can appear an odd number of times (which would be the center character in the case of strings with an odd length), and all other characters must appear an even number of times. Use this fact to decide whether a palindrome can be formed, and if yes, construct one by arranging half the characters in sorted order, placing the odd-count character (if any) in the middle, and then appending the reverse of the first half.

Note: If multiple valid palindromes are possible, any one of them is accepted.

inputFormat

The input consists of a single line containing the string s.

Example: ivicc

outputFormat

If a palindrome can be formed by rearranging the string, output one valid palindrome. Otherwise, output Not possible.

Example: For the input ivicc, a valid output is civic.

civic

civic