#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const ll inf = 1e18 + 1;
const int maxn = 2011;
int DP[maxn][maxn];
ll num[maxn][maxn];
bool ok[maxn][maxn];
char S[maxn];
int n;

int GetDP(int l, int r){
    if (ok[l][r]) return DP[l][r];
    ok[l][r] = 1;
    if (l == r){
        DP[l][r] = 0;
        num[l][r] = 1;
        return 0;
    }
    if (l == r - 1 && S[l] == S[r]){
        DP[l][r] = 0;
        num[l][r] = 1;
        return 0;
    }
    if (S[l] == S[r]){
        DP[l][r] = GetDP(l+1, r-1);
        num[l][r] = num[l+1][r-1];
        return DP[l][r];
    }
    else{
        int ll = GetDP(l+1, r) + 1, rr = GetDP(l, r-1) + 1;
        DP[l][r] = min(ll, rr);
        if (ll < rr)
            num[l][r] = num[l+1][r];
        else if (rr < ll)
            num[l][r] = num[l][r-1];
        else
            num[l][r] = num[l+1][r] + num[l][r-1];

        num[l][r] = min(inf, num[l][r]);
        return DP[l][r];
    }
}
char ans[maxn*2];
int tot = 0;
void print1(){
    rep(i, 1, tot)
        printf("%c",ans[i]);
}
void print2(){
    for (int i = tot; i >= 1; i--)
        printf("%c",ans[i]);
    printf("\n");
}
void Getans(int l, int r, ll k){
    if (num[l][r] < k){
        printf("NONE\n");
        return;
    }
    if (l == r){
        print1();
        printf("%c",S[l]);
        print2();
        return;
    }
    if (S[l] == S[r] && l == r - 1){
        ans[++tot] = S[l];
        print1();
        print2();
        return;
    }
    if (S[l] == S[r]){
        ans[++tot] = S[l];
        Getans(l + 1, r - 1, k);
    }
    else{
        if (DP[l+1][r] < DP[l][r-1]){
            ans[++tot] = S[l];
            Getans(l+1, r, k);
        }
        else if (DP[l][r-1] < DP[l+1][r]){
            ans[++tot] = S[r];
            Getans(l, r-1, k);
        }
        else{
            if (S[l] < S[r]){
                if (num[l+1][r] >= k){
                    ans[++tot] = S[l];
                    Getans(l+1,r,k);
                }
                else{
                    k -= num[l+1][r];
                    ans[++tot] = S[r];
                    Getans(l,r-1,k);
                }
            }
            else{
                if (num[l][r-1] >= k){
                    ans[++tot] = S[r];
                    Getans(l,r-1,k);
                }
                else{
                    k -= num[l][r-1];
                    ans[++tot] = S[l];
                    Getans(l+1,r,k);
                }
            }
        }
    }
}
int main(){
    scanf("%s", S + 1);
    n = strlen(S + 1);
    ll k;
    cin>>k;
    GetDP(1, n);
    Getans(1, n, k);
    return 0;
}
### Prompt

Your challenge is to write a Cpp solution to the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const ll inf = 1e18 + 1;
const int maxn = 2011;
int DP[maxn][maxn];
ll num[maxn][maxn];
bool ok[maxn][maxn];
char S[maxn];
int n;

int GetDP(int l, int r){
    if (ok[l][r]) return DP[l][r];
    ok[l][r] = 1;
    if (l == r){
        DP[l][r] = 0;
        num[l][r] = 1;
        return 0;
    }
    if (l == r - 1 && S[l] == S[r]){
        DP[l][r] = 0;
        num[l][r] = 1;
        return 0;
    }
    if (S[l] == S[r]){
        DP[l][r] = GetDP(l+1, r-1);
        num[l][r] = num[l+1][r-1];
        return DP[l][r];
    }
    else{
        int ll = GetDP(l+1, r) + 1, rr = GetDP(l, r-1) + 1;
        DP[l][r] = min(ll, rr);
        if (ll < rr)
            num[l][r] = num[l+1][r];
        else if (rr < ll)
            num[l][r] = num[l][r-1];
        else
            num[l][r] = num[l+1][r] + num[l][r-1];

        num[l][r] = min(inf, num[l][r]);
        return DP[l][r];
    }
}
char ans[maxn*2];
int tot = 0;
void print1(){
    rep(i, 1, tot)
        printf("%c",ans[i]);
}
void print2(){
    for (int i = tot; i >= 1; i--)
        printf("%c",ans[i]);
    printf("\n");
}
void Getans(int l, int r, ll k){
    if (num[l][r] < k){
        printf("NONE\n");
        return;
    }
    if (l == r){
        print1();
        printf("%c",S[l]);
        print2();
        return;
    }
    if (S[l] == S[r] && l == r - 1){
        ans[++tot] = S[l];
        print1();
        print2();
        return;
    }
    if (S[l] == S[r]){
        ans[++tot] = S[l];
        Getans(l + 1, r - 1, k);
    }
    else{
        if (DP[l+1][r] < DP[l][r-1]){
            ans[++tot] = S[l];
            Getans(l+1, r, k);
        }
        else if (DP[l][r-1] < DP[l+1][r]){
            ans[++tot] = S[r];
            Getans(l, r-1, k);
        }
        else{
            if (S[l] < S[r]){
                if (num[l+1][r] >= k){
                    ans[++tot] = S[l];
                    Getans(l+1,r,k);
                }
                else{
                    k -= num[l+1][r];
                    ans[++tot] = S[r];
                    Getans(l,r-1,k);
                }
            }
            else{
                if (num[l][r-1] >= k){
                    ans[++tot] = S[r];
                    Getans(l,r-1,k);
                }
                else{
                    k -= num[l][r-1];
                    ans[++tot] = S[l];
                    Getans(l+1,r,k);
                }
            }
        }
    }
}
int main(){
    scanf("%s", S + 1);
    n = strlen(S + 1);
    ll k;
    cin>>k;
    GetDP(1, n);
    Getans(1, n, k);
    return 0;
}
```