Smallest Palindrome Rearrangement

You are given a string s consisting of lowercase letters. Your task is to determine whether the characters of s can be rearranged to form a palindrome. If it is possible, output the lexicographically smallest palindrome that can be formed. Otherwise, output an empty string.

A palindrome is a string that reads the same backward as forward. The lexicographically smallest palindrome is the one that would appear first in a dictionary ordering. For example, rearranging "aabb" can result in "abba" which is the smallest possible palindrome.

Note: Input is provided via standard input and output must be printed to standard output.

inputFormat

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

Example:

aabb

outputFormat

Output the lexicographically smallest palindrome that can be formed from the input string if possible. Otherwise, output an empty string.

Example:

abba

## sample

aabb

abba

</p>