#include <bits/stdc++.h>
using namespace std;

using ll = long long int;
constexpr int INF = 1<<30;

ll n ,k;
string s;

int dp[2005][2005];  // dp[l][r]: 文字列Sの区間[l,r]を部分列に含む回文の最小長さ
ll dp2[2005][2005];  // dp[l][r]: 文字列Sの区間[l,r]を部分列に含む最小長の回文の個数

// 回文の最小長さを求める [l,r]
int rec(int l, int r){
    if(l == r) return dp[l][r] = 1;
    if(l > r) return 0;
    if(dp[l][r] > 0) return dp[l][r];
    int res = INF;
    if(s[l] == s[r]) res = min(res, rec(l+1,r-1)+2);
    else{
        res = min(res, rec(l,r-1)+2);
        res = min(res, rec(l+1,r)+2);
    }
    return dp[l][r] = res;
}

// 回文の個数を数える [l,r]
ll rec2(int l, int r){
    if(l >= r) return dp2[l][r] = 1;
    if(dp2[l][r] >= 0) return dp2[l][r];
    ll res = 0;
    if(s[l] == s[r]){
        res += rec2(l+1,r-1);
    }else{
        if(dp[l][r] == dp[l][r-1]+2) res += rec2(l,r-1);
        if(dp[l][r] == dp[l+1][r]+2) res += rec2(l+1,r);
    }
    return dp2[l][r] = min(res, k+10);
}

// 辞書順でk番目を求める
string rec3(int l, int r, ll m){
    if(l == r) return s.substr(l,1);
    if(l > r) return "";
    string res;
    if(s[l] == s[r]){
        res = rec3(l+1,r-1, m);
        res.insert(res.begin(),s[l]);
        res.push_back(s[r]);
    }else{
        if(s[l] < s[r]){
            if(dp[l][r] != dp[l+1][r]+2 || dp2[l+1][r] <= m){
                res = rec3(l,r-1,m-(dp[l][r] != dp[l+1][r]+2 ? 0 : dp2[l+1][r]));
                res.insert(res.begin(),s[r]);
                res.push_back(s[r]);
            }else{
                res = rec3(l+1,r,m);
                res.insert(res.begin(),s[l]);
                res.push_back(s[l]);
            }
        }else{
            if(dp[l][r] != dp[l][r-1]+2 || dp2[l][r-1] <= m){
                res = rec3(l+1,r,m-(dp[l][r] != dp[l][r-1]+2 ? 0 : dp2[l][r-1]));
                res.insert(res.begin(),s[l]);
                res.push_back(s[l]);
            }else{
                res = rec3(l,r-1,m);
                res.insert(res.begin(),s[r]);
                res.push_back(s[r]);
            }
        }
    }
    return res;
}

int main(){
    cin >> s >> k;
    n = s.size();
    rec(0,n-1);
    for(int i=0;i<n;i++) fill(dp2[i], dp2[i]+n, -1);
    if(rec2(0,n-1) < k){
        cout << "NONE\n";
    }else{
        cout << rec3(0,n-1,k-1) << "\n";
    }
    return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long int;
constexpr int INF = 1<<30;

ll n ,k;
string s;

int dp[2005][2005];  // dp[l][r]: 文字列Sの区間[l,r]を部分列に含む回文の最小長さ
ll dp2[2005][2005];  // dp[l][r]: 文字列Sの区間[l,r]を部分列に含む最小長の回文の個数

// 回文の最小長さを求める [l,r]
int rec(int l, int r){
    if(l == r) return dp[l][r] = 1;
    if(l > r) return 0;
    if(dp[l][r] > 0) return dp[l][r];
    int res = INF;
    if(s[l] == s[r]) res = min(res, rec(l+1,r-1)+2);
    else{
        res = min(res, rec(l,r-1)+2);
        res = min(res, rec(l+1,r)+2);
    }
    return dp[l][r] = res;
}

// 回文の個数を数える [l,r]
ll rec2(int l, int r){
    if(l >= r) return dp2[l][r] = 1;
    if(dp2[l][r] >= 0) return dp2[l][r];
    ll res = 0;
    if(s[l] == s[r]){
        res += rec2(l+1,r-1);
    }else{
        if(dp[l][r] == dp[l][r-1]+2) res += rec2(l,r-1);
        if(dp[l][r] == dp[l+1][r]+2) res += rec2(l+1,r);
    }
    return dp2[l][r] = min(res, k+10);
}

// 辞書順でk番目を求める
string rec3(int l, int r, ll m){
    if(l == r) return s.substr(l,1);
    if(l > r) return "";
    string res;
    if(s[l] == s[r]){
        res = rec3(l+1,r-1, m);
        res.insert(res.begin(),s[l]);
        res.push_back(s[r]);
    }else{
        if(s[l] < s[r]){
            if(dp[l][r] != dp[l+1][r]+2 || dp2[l+1][r] <= m){
                res = rec3(l,r-1,m-(dp[l][r] != dp[l+1][r]+2 ? 0 : dp2[l+1][r]));
                res.insert(res.begin(),s[r]);
                res.push_back(s[r]);
            }else{
                res = rec3(l+1,r,m);
                res.insert(res.begin(),s[l]);
                res.push_back(s[l]);
            }
        }else{
            if(dp[l][r] != dp[l][r-1]+2 || dp2[l][r-1] <= m){
                res = rec3(l+1,r,m-(dp[l][r] != dp[l][r-1]+2 ? 0 : dp2[l][r-1]));
                res.insert(res.begin(),s[l]);
                res.push_back(s[l]);
            }else{
                res = rec3(l,r-1,m);
                res.insert(res.begin(),s[r]);
                res.push_back(s[r]);
            }
        }
    }
    return res;
}

int main(){
    cin >> s >> k;
    n = s.size();
    rec(0,n-1);
    for(int i=0;i<n;i++) fill(dp2[i], dp2[i]+n, -1);
    if(rec2(0,n-1) < k){
        cout << "NONE\n";
    }else{
        cout << rec3(0,n-1,k-1) << "\n";
    }
    return 0;
}

```