На этот раз Гусейн планирует подарить своему другу Азеру подарок на день рождения с написанным на нем словом палиндром. Но чтобы подарок был ценным, он хочет, чтобы это слово было лексикографически как можно большим. В настоящее время на подарке маленькими английскими буквами написано слово $s$. Слово $s$ возможно, не является палиндромом. Однако слово, написанное на подарке Гусейна, должно быть палиндромом, иначе Азер не будет ему рад. Гусейн может заменить любую букву в слове $s$ другой строчной английской буквой. Это занимает у него $1$ минуту. Он сможет сделать это не более $k$ раз, потому что через $k$ минут он подарит подарок Азеру. Найдите лексикографически наибольшее слово-палиндром, которое Гусейн сможет написать на подарке, который он преподнесет Азеру. Если Гусейн не может составить слово-палиндром, то выведите :(. \textbf{Примечание 1}. Слова, которые читаются одинаково от начала до конца и от конца до начала, называются палиндромами. Например, \textbf{radar} является палиндромом, а \textbf{rfo} нет. \textbf{Примечание 2}. Слово $x$ одинаковой длины считается лексикографически большим, чем слово $y$, если существует $i$ такое, что оба слова одинаковы перед $i$-м символом, но $i$-й символ в $x$ больше, чем $i$-й символ $y$. \InputFile В первой строке дано слово $s~(1 \le |s| \le 10^5)$, состоящее из строчных английских букв. Во второй строке записано целое число $k~(0 \le k \le |s|)$. \OutputFile Выведите лексикографически наибольшее слово-палиндром, которое Гусейн сможет написать на подарке Азера. Если это невозможно, то выведите :(.