/*
 * 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
 */

void _print(const set<size_t>& v) {
    for_each(
        v.begin(),
        v.end(),
        [](int t) { cout << t << " "; }
    );
    cout << endl;
}

set<size_t> _f(const string& s) {
    set<size_t> rx;
    size_t n = s.size();
    size_t k = static_cast<size_t>(floor(n / 2));
    size_t j;
    for (size_t i = 0; i < k; ++i) {
        j = n - 1 - i;
        if (s[i] != s[j]) {
            rx.insert(i);
        }
    }
    return rx;
}

char lx(char c1, char c2) {
    return (c1 > c2) ? c1 : c2;
}

string highestValuePalindrome(string s, int n, int k) {
    
    if (k >= n) {
        return string(n, '9');
    }

    size_t i, j;
    
    auto ix = _f(s);
    // _print(ix);
    if (ix.size() > k) { return "-1"; }
    
    for (auto ii: ix) {
        j = n - 1 - ii;
        auto c = lx(s[ii], s[j]);
        s[ii] = c;
        s[j] = c;
        k--;        
    }

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

    if ((k > 0) && (n % 2 == 1)) {
        j = static_cast<size_t>((n - 1) / 2);
        s[j] = '9';
        k--;
    }
    
    return s;
}