Максимальный палиндром

На этот раз Гусейн планирует подарить своему другу Азеру подарок на день рождения с написанным на нем словом палиндром. Но чтобы подарок был ценным, он хочет, чтобы это слово было лексикографически как можно большим.

В настоящее время на подарке маленькими английскими буквами написано слово $s$. Слово $s$ возможно, не является палиндромом. Однако слово, написанное на подарке Гусейна, должно быть палиндромом, иначе Азер не будет ему рад.

Гусейн может заменить любую букву в слове $s$ другой строчной английской буквой. Это занимает у него $1$ минуту. Он сможет сделать это не более $k$ раз, потому что через $k$ минут он подарит подарок Азеру.

Найдите лексикографически наибольшее слово-палиндром, которое Гусейн сможет написать на подарке, который он преподнесет Азеру. Если Гусейн не может составить слово-палиндром, то выведите :(.

Примечание 1. Слова, которые читаются одинаково от начала до конца и от конца до начала, называются палиндромами. Например, radar является палиндромом, а rfo нет.

Примечание 2. Слово $x$ одинаковой длины считается лексикографически большим, чем слово $y$, если существует $i$ такое, что оба слова одинаковы перед $i$-м символом, но $i$-й символ в $x$ больше, чем $i$-й символ $y$.

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

В первой строке дано слово $s(1\le |s|\le 10^5)$, состоящее из строчных английских букв. Во второй строке записано целое число $k(0\le k\le |s|)$.

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

Выведите лексикографически наибольшее слово-палиндром, которое Гусейн сможет написать на подарке Азера. Если это невозможно, то выведите :(.

Примеры