Example

Input

crc
1


Output

crc
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long int;

const ll INF = 1LL << 60;
const int L = 2010;
ll dp[L][L], num[L][L];

void update_dp(int nl, int nr, int pl, int pr, ll a) {
    if(dp[nl][nr] > dp[pl][pr] + a) {
        dp[nl][nr] = dp[pl][pr] + a;
        num[nl][nr] = num[pl][pr];
    }
    else if(dp[nl][nr] == dp[pl][pr] + a) {
        num[nl][nr] += num[pl][pr];
    }
    num[nl][nr] = min(num[nl][nr], INF);
}

int main() {
    string s; cin >> s;
    ll K; cin >> K;

    int N = s.size();
    fill(dp[0], dp[N+1], INF);
    for(int i=0; i<=N; i++) dp[i][i] = 0, num[i][i] = 1;
    for(int i=0; i<N; i++) dp[i][i+1] = 0, num[i][i+1] = 1;

    for(int d=2; d<=N; d++) {
        for(int l=0; l<=N-d; l++) {
            int r = l + d;
            if(s[l] == s[r-1]) {
                update_dp(l, r, l+1, r-1, 0);
            }
            else {
                update_dp(l, r, l+1, r, 1);
                update_dp(l, r, l, r-1, 1);
            }
        }
    }

    if(num[0][N] < K) {
        cout << "NONE" << endl;
        return 0;
    }
    
    int l = 0, r = N;
    string ans = "";

    while(r - l > 1) {
        if(s[l] == s[r-1]) {
            ans += s[l];
            l++; r--;
        }
        else if(dp[l+1][r] < dp[l][r-1]) {
            ans += s[l];
            l++;
        }
        else if(dp[l][r-1] < dp[l+1][r]) {
            ans += s[r-1];
            r--;
        }
        else if(s[l] < s[r-1]) {
            if(K <= num[l+1][r]) {
                ans += s[l];
                l++;
            }
            else {
                K -= num[l+1][r];
                ans += s[r-1];
                r--;
            }
        }
        else if(s[r-1] < s[l]) {
            if(K <= num[l][r-1]) {
                ans += s[r-1];
                r--;
            }
            else {
                K -= num[l][r-1];
                ans += s[l];
                l++;
            }
        }
    }
    
    string res = "";
    res += ans;
    if(r - l == 1) res += s[l];
    reverse(ans.begin(), ans.end()); res += ans;
    cout << res << endl;
}

