C. Сделай палиндром
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка называется палиндромом, если она одинаково читается слева-направо и справа-налево. Например, строки «kazak», «oo», «r» и «mikhailrubinchikkihcniburliahkim» — палиндромы, а строки «abb» и «ij» — нет.

Замена символа — это выбор позиции символа в строке и замена символа в этой позиции на произвольную другую строчную букву. Таким образом, при замене символа длина строки не изменяется.

Задана строка s. Вы можете сначала заменить в строке s некоторые символы, а затем произвольным образом поменять местами порядок символов в строке. Изменение порядка не считается заменами.

Необходимо получить палиндром за наименьшее количество замен. Если это возможно сделать несколькими способами, то нужно получить лексикографически наименьший палиндром. Таким образом в первую очередь необходимо минимизировать количество замененных символов, а среди таких способов найти какой наименьший лексикографически (алфавитно) палиндром можно получить в результате.

Входные данные

В единственной строке входных данных находится строка s (1 ≤ |s| ≤ 2·105), состоящая из строчных латинских букв.

Выходные данные

Выведите лексикографически наименьший палиндром, который можно получить за наименьшее количество замен.

Примеры
Входные данные
aabc
Выходные данные
abba
Входные данные
aabcd
Выходные данные
abcba