Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Палиндромом называется строка, одинаково читающаяся как слева направо, так и справа налево. Так, например, слова «ротор», «дед», «заказ» являются палиндромами.
У Максима есть слово S, и он очень хочет сделать из него палиндром, но не желает изменять слишлом большое количество символов. Помогите Максиму найти лексикографически минимальный палиндром, который можно получить из слова S заменой не более чем K символов.
Строка A лексикографически меньше строки B, если существует такой индекс j, что A[j] < B[j] и ∀i < j A[i] = B[i].
Входные данные
Первая строка содержит слово S, состоящее из строчных латинских букв и имеющее длину не более 10^5 символов.
Вторая строка содержит целое число K (0 <= K <= 10^5) — максимально возможное количество замен.
Выходные данные
В единственной строке выведите ответ на задачу. Если сформировать палиндром невозможно, выведите NO.
Примеры
| Входные данные | Выходные данные |
ozoxo
1 | oxoxo |
abaac
4 | aaaaa |
Для отправки решений необходимо выполнить вход.
|