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

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

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

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