На дверце холодильника висят магниты с латинскими буквами: на каждом магните — одна строчная буква, некоторые буквы повторяются. Маша хочет выложить из магнитов палиндром — слово, которое одинаково читается слева направо и справа налево, например level или abba. Смысл слова значения не имеет: подходит любая последовательность букв. Использовать все магниты не обязательно, но каждый магнит можно взять только один раз.
Палиндром должен быть как можно длиннее. Если самых длинных палиндромов несколько, Маша выберет тот, который стоял бы в словаре раньше остальных, то есть лексикографически наименьший.
Формат входных данных
В единственной строке записана непустая строка длиной не более 100 000, состоящая из строчных латинских букв, — буквы на магнитах.
Формат выходных данных
Выведите палиндром наибольшей длины, который можно выложить из данных букв. Если таких палиндромов несколько, выведите лексикографически наименьший.
Определение. Из двух различных строк одинаковой длины лексикографически меньше та, у которой в первой слева позиции, где строки различаются, стоит буква, расположенная в алфавите раньше.
Пояснение к первому примеру. Строка abacaba сама является палиндромом длины 7, но из тех же букв можно выложить палиндром aabcbaa той же длины, и он лексикографически меньше.
| № | Входные данные | Выходные данные |
|
1
|
abacaba
|
aabcbaa
|
|
2
|
zyx
|
x
|
|
3
|
bbaacc
|
abccba
|