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]