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 :(.

Note 1. Words that read the same forward and backward are called palindromes. For example, radar is a palindrome, but rfo is not.

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$.

Input

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|)$.

Output

Print the lexicographically largest palindrome that Huseyn can write on Azar's gift. If this is not possible, print :(.

Examples