Oh goodness... Sean accidentally mixed up his eggs with a can of alphabet soup, and now everything's all scrambled together! Now he needs your help to rearrange the letters in the alphabet soup and restore peace to the egg-iverse.
Sean's suspicious egg-soup mixture can be represented as a series of $$$n$$$ spaghetti letters. He knows that two conditions used to be true of his letters before they got scrambled into the eggs:
- When put in a row, his letters would form a palindrome, a string which is read the same forwards and backwards. Put more formally, if his letters were labelled $$$s_1, s_2, \dots, s_n$$$, then it is the case that $$$s_i = s_{n - i + 1}$$$ for each $$$i \in \{1, 2, \dots, n\}$$$.
- Of all possible palindromes, his letters would form the lexicographically smallest one.
Sean knows for certain that it is possible for him to arrange the scrambled up spaghetti letters to fulfill both constraints simultaneously, but he's busy at the moment researching possible egg-spaghetti hybrids, and needs your help to unscramble his soup!
The input will consist of a single line containing a single string of length $$$n$$$ ($$$1 \leq n \leq 10^5$$$) consisting exclusively of lowercase English letters — the scrambled-up spaghetti letters found in Sean's egg soup.
The output should consist of a single line containing a single string representing the unscrambled contents of Sean's egg soup as described by the rules above.
racecar
acrerca
aabbccdde
abcdedcba
ajcvoiwqnexajcvoiwqnex
aceijnoqvwxxwvqonjieca
- In the first sample test case, "racecar" itself is a palindrome, but not the lexicographically smallest palindrome which can be created using the same set of letters.
- In the second sample test case, the letters are already arranged in lexicographical order, but they do not immediately form a palindrome.
