string highestValuePalindrome(string s, int n, int k) 
{
    int i = 0;
    std::set< int > visited;
    
    while ( i < s.size() )
    {
        if ( s[ i ] != s[ n - i - 1 ] )
        {
            if ( k == 0 ) return "-1";
            auto value = std::max( s[ i ], s[ n - i - 1 ] );
            s[ i ] = s[ n - i - 1 ] = value;
            k--;
            visited.insert( i );
        }
        i++;
    }

    // in here s is a palindrome

    i = 0;
    while ( i < s.size() && k > 0 )
    {
        if ( s[ i ] != '9' )
        {
            if ( visited.find( i ) != visited.end() )
            {
                s[ i ] = s[ n - i - 1 ] = '9';
                k--;
            }
            else if ( k >= 2 )
            {
                s[ i ] = s[ n - i - 1 ] = '9';
                k -= 2;
            }
        }
        
        i++;
    }
    
    if ( n % 2 == 1 && k > 0 ) s[ n/2 ] = '9';

    return s;
}