This time Huseyn plans to give his friend Azar a birthday present with a palindrome word written on it. But to make the gift valuable, he wants the word to be as large as possible lexicographically. Currently, the gift has a word $s$ written on it in small English letters. The word $s$ may not be a palindrome. However, the word written on Huseyn's gift must be a palindrome, otherwise Azar will not be happy with it. Huseyn can replace any letter in the word $s$ with another lowercase English letter. It takes him $1$ minute to do so. He can do this no more than $k$ times because in $k$ minutes, he will present the gift to Azar. Find the lexicographically largest palindrome that Huseyn can write on the gift he will present to Azar. If Huseyn cannot create a palindrome, print :(. \textbf{Note 1}. Words that read the same forward and backward are called palindromes. For example, \textbf{radar} is a palindrome, but \textbf{rfo} is not. \textbf{Note 2}. A word $x$ of the same length is considered lexicographically greater than a word $y$ if there exists an index $i$ such that both words are identical up to the $i$-th character, but the $i$-th character in $x$ is greater than the $i$-th character in $y$. \InputFile The first line contains a word $s~(1 \le |s| \le 10^5)$, consisting of lowercase English letters. The second line contains an integer $k~(0 \le k \le |s|)$. \OutputFile Print the lexicographically largest palindrome that Huseyn can write on Azar's gift. If this is not possible, print :(.