Example

Input

crc
1


Output

crc
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;

int main(){
    string s;
    lli k;
    cin >> s >> k;
    int n = s.length();
    // len, num;
    vector<vector<pair<int, lli>>> dp(n, vector<pair<int, lli>>(n+1));
    for(int i=0; i<n; i++){
        dp[i][i] = {0, 1LL};
        dp[i][i+1] = {1, 1LL};
    }
    for(int w=2; w<n+1; w++){
        for(int i=0; i+w<n+1; i++){
            if(s[i] == s[i+w-1]){
                auto tmp = dp[i+1][i+w-1];
                dp[i][i+w] = {tmp.first +2, tmp.second};
            }else{
                auto tmp1 = dp[i][i+w-1];
                auto tmp2 = dp[i+1][i+w];
                if(tmp1.first > tmp2.first) swap(tmp1, tmp2);
                if(tmp1.first == tmp2.first){
                    dp[i][i+w] = {tmp1.first +2, min(tmp1.second +tmp2.second, k+1)};
                }else{
                    dp[i][i+w] = {tmp1.first +2, tmp1.second};
                }
            }
        }
    }
    if(dp[0][n].second < k){
        cout << "NONE" << endl;
        return 0;
    }
    int i=0,j=n;
    string front="",mid="";
    while(1){
        if(i == j) break;
        if(i+1 == j){
            mid += s[i];
            break;
        }
        if(s[i] == s[j-1]){
            front += s[i];
            i++; j--;
        }else if(dp[i+1][j].first < dp[i][j-1].first){
            front += s[i];
            i++;
        }else if(dp[i+1][j].first > dp[i][j-1].first){
            front += s[j-1];
            j--;
        }else if(s[i] < s[j-1]){
            if(dp[i+1][j].second >= k){
                front += s[i];
                i++;
            }else{
                k -= dp[i+1][j].second;
                front += s[j-1];
                j--;
            }
        }else{
            if(dp[i][j-1].second >= k){
                front += s[j-1];
                j--;
            }else{
                k -= dp[i][j-1].second;
                front += s[i];
                i++;
            }
        }
    }
    string back = front;
    reverse(back.begin(), back.end());
    cout << front << mid << back << endl;
    return 0;
}

