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.
The first line contains a word s (1≤∣s∣≤105), consisting of lowercase English letters. The second line contains an integer k (0≤k≤∣s∣).
Print the lexicographically largest palindrome that Huseyn can write on Azar's gift. If this is not possible, print :(.