Problems
Maximum palindrome
Maximum palindrome
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 :(.
Input example #1
rfo 1
Output example #1
rfr
Input example #2
aabb 1
Output example #2
:(
Input example #3
kabab 2
Output example #3
zabaz
Input example #4
abacaba 0
Output example #4
abacaba