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

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

Зараз на подарунку маленькими англійськими літерами написане слово $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|)$.

Вихідні дані

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

Приклади