"""
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)