#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'highestValuePalindrome' function below.
#
# The function is expected to return a STRING.
# The function accepts following parameters:
#  1. STRING s
#  2. INTEGER n
#  3. INTEGER k
#
_marks=[]
def _create_palindrom(s):
    count=0
    s=list(s)
    for i in range(len(s)//2):
        #check string
        if (s[i]<s[len(s)-i-1]):
            count+=1
            s[i]=s[len(s)-i-1]
            _marks.append(i)
        elif s[i]>s[len(s)-i-1]:
            s[len(s)-i-1]=s[i]
            count+=1
            _marks.append(i)
    return s, count
            
    
def _maximize_palindrome(s, k, count):
   if k>0 and len(s)==1:
       s[0]='9'
       return
   for i in range(len(s)//2):
       #change the current symbol
       if k>1 and s[i]<'9' and i not in _marks:
           s[i]='9'
           s[len(s)-i-1]='9'
           k-=2
       elif count>0 and s[i]<'9' and i in _marks:    
            s[i]='9'
            s[len(s)-i-1]='9'
            if count>1:
               count-=2
            else:
                count-=1
                k-=1
   #change the middle         
   if k==1 and len(s)%2>0 and count>=0:
         s[len(s)//2]='9'
           
           

def highestValuePalindrome(s, n, k):
    res, count=_create_palindrom(s)
    if count>k:
        return '-1'
    if count<k:
        _maximize_palindrome(res, k-count, count) 
    return ''.join(res)
    
    # Write your code here

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    k = int(first_multiple_input[1])

    s = input()

    result = highestValuePalindrome(s, n, k)

    fptr.write(result + '\n')

    fptr.close()

"""
The code fails for long strings probably because the environment times out but I ran locally and it's working as expected
"""

def highestValuePalindrome(s, n, k): 
    # Write your code here
    count = 0
    sarr = [c for c in s]
    for i in range(n//2):
        if sarr[i] == sarr[n-1-i] and sarr[i] != '9' and k>1:            
                sarr[i] = '9'
                sarr[n-i-1] = '9'
                k-=2
        elif sarr[i] == sarr[n-1-i] and k == 1:
            continue
        elif sarr[i] != sarr[n-1-i] and k > 1:
            if sarr[i] == '9':
                sarr[n-1-i] = '9'
                k -= 1
            elif sarr[n-1-i] == '9':
                sarr[i] = '9'
                k -= 1
            else:
                sarr[i] = '9'
                sarr[n-i-1] = '9'
                k-=2
            
        elif sarr[i] != sarr[n-1-i] and k == 1:
            if sarr[i] > sarr[n-1-i]:
                sarr[n-1-i] = sarr[i]
            else:
                sarr[i] = sarr[n-1-i]
            k -= 1
        if k == 0:
            break
    if k == 1:
        if sarr[n//2] != '9':
            sarr[n//2] = '9'
            k -= 1
    print(sarr)
    retval = 0
    for i in range(n//2):
        if sarr[i] != sarr[n-1-i]:
            retval = -1
            print("will return -1")
    if retval <0:
        return str(retval)
    else:
        return ''.join(sarr)

Problem Breakdown:
Input: A string of digits s and an integer k, which is the maximum number of allowed changes.
Output: The largest possible palindrome that can be formed by modifying at most k digits.
A palindrome is a sequence that reads the same forwards and backwards. The task is to modify the string to make it a palindrome and ensure it's the largest possible palindrome while adhering to the constraint of making at most k changes.

Approach:
Palindrome Formation:

The first step is to ensure the string is a palindrome. For each pair of characters at positions i and n-i-1, if they aren't the same, you'll need to modify one of them to make them match.
Maximizing the Palindrome:

Once you've created a valid palindrome, to maximize its value, you can replace characters to make the digits as large as possible (preferably '9's). This should be done while respecting the maximum number of allowed changes, k.
Greedy Strategy:

First, convert the string to a valid palindrome with the minimum number of changes.
Then, greedily try to make the string the largest possible palindrome by prioritizing making digits '9' if you still have remaining changes.
Steps:
First Pass: Make the string a valid palindrome by checking pairs of characters.
Second Pass: Maximize the palindrome by replacing characters with '9' if you have enough remaining changes.
Edge Case Handling: If k is too small to make any changes, return the original string

def highestValuePalindrome(s, n, k):
    sArr = list(s)
    half = (n >> 1) + 1
    count = k
    
    # check non-palindrome
    idxL, idxR = 0, n - 1
    while idxL <= idxR:
        if sArr[idxL] != sArr[idxR]:
            # use the max value of them
            sArr[idxL] = sArr[idxR] = max(sArr[idxL], sArr[idxR])
            count -= 1
        # if there are more than k invalid digits, return -1 
        if count < 0:
            return '-1'
        idxL, idxR = idxL + 1, idxR - 1
        
    # repalce 9
    idxL, idxR = 0, n - 1
    while idxL <= idxR:
        if idxL == idxR:
            # if it is the middle one(odd length), try to set the digit to 9
            if count > 0:
                sArr[idxL] = '9'
        else:
            deduct = 0
            if sArr[idxL] < '9':
                # set the pair of digits to 9 if it is necessary
                if sArr[idxL] != s[idxL] or sArr[idxR] != s[idxR]:
                    # if this pair of digits are invalid, reduce by 1, 
                    # because the counter has already decrased by 1 before
                    deduct = 1
                else:
                    # otherwise, decrease the counter by 2
                    deduct = 2
                    
                # if the counter is still greater or equals to 0, execute it  
                if (count - deduct) >= 0:
                    sArr[idxL] = sArr[idxR] = '9'
                    count -= deduct
                    
        idxL, idxR = idxL + 1, idxR - 1
    
    return ''.join(sArr)

import collections
def highestValuePalindrome(s, n, k):
    if n == 1: #Easily solvable if n = 1
        if k >= 1:
            return "9"
        else:
            return s
    #Get a string of the pure completed palindrome, along with an array of extra changes needed for both numbers to become "9"
    half = int(n//2)
    string = ""
    extra_steps = collections.deque()
    for i in range(half):
        left, right = s[i], s[n-1-i]
        change = 0
        if left != right: #Fixed needed if not matching
            k -= 1
            if k < 0: #No need to continue if impossible
                break
            #If neither are "9", then need one extra change to become "9"
            if left != "9" and right != "9":
                change = 1
        #If matching and not equal to "9", two extra changes are needed to become "9"
        elif left != "9":
            change = 2
        string += max(left, right) #Add the highest value
        if k - change < 0: #Can't change to "9" if not enough moves are available
            change = 0
        extra_steps.append(change)
    if k < 0: #Failed if k < 0
        return "-1"
    steps = 0 #Also the index
    high_string = ""
    for x in extra_steps:
        if k - x >= 0 and x > 0: #No change if not enough attemps or there are no changes
            high_string += "9"
            k -= x
        else:
            high_string += string[steps]
        steps += 1
    if n%2 == 1: #Check if there is a middle digit
        if k > 0: #Can change to "9" if there is still changes possible
            middle = "9"
        else: #Otherwise the original middle
            middle = s[half]
    else: #There is no middle
        middle = ""
    return high_string + middle + high_string[::-1]