string makePalindrome(string s, int n, int k,bool odd,string first,string second,int diff){
    string result;

    //rest will be number of extra changes we can do in palindrome
    int rest=k-diff;

    //this map will show if the index is included in making normal palindrome
    unordered_map<int,bool> included;

    for(int i=0;i<n/2;i++){
        if(first[i] != second[n/2-i-1]){
            if(first[i]>second[n/2-i-1])
                second[n/2-1-i]=first[i];
            else
                first[i]=second[n/2-1-i];
            included[i]=true;   //include the index if it is changed
        }
    }

    for(int i=0;i<n/2;i++){
        //if the index is not included then rest will be deducted by 2
        if(first[i]!='9' && !included[i]){
            rest-=2;
            if(rest<0){
                rest+=2;
                continue;
            }
            //setting the changed index
            first[i]=second[n/2-i-1]='9';
        }
        //else by 1
        else if(first[i]!='9' && included[i]){
            rest--;
            if(rest<0){
                rest++;
                continue;
            }
            first[i]=second[n/2-i-1]='9'; 
        } 
    }

    if(odd){
        if(rest)
            s[n/2]='9';
    }

    if(odd)
        result=first+s[n/2]+second;
    else
        result=first+second;

    return result;
}

// Complete the highestValuePalindrome function below.
string highestValuePalindrome(string s, int n, int k) {
    if(n==1){
        if(k>0)
            return "9";
        else if(k==0)
            return s;
        else
            return "-1";
    }
    
    string first,second,result;
    int len=n/2;
    bool odd;
    if(n%2==0)
        odd=false;
    else
        odd=true;

    first.assign(s,0,n/2);
    if(odd)
        second.assign(s,n/2+1,n); 
    else
        second.assign(s,n/2,n);
    
    int different=0;
    for(int i=0;i<n/2;i++){
        if(first[i] != second[n/2-i-1]){
            different++;
        }
    }

    if(k<different)
        return "-1";
    else
        result=makePalindrome(s,n,k,odd,first,second,different);

    return result;
}