#include <iostream>
#include<math.h>
#include<vector>
# include<string.h>
#include <queue>
#include <cstdio>
using namespace std;
const int maxn=2010;
const int INF=10000;
typedef long long LL;
int dp[maxn][maxn];
LL way[maxn][maxn];
int n;
LL k;
char s[maxn];

void dfs(int L,int R){
    if(L>=R) {dp[L][R]=0;way[L][R]=1;return;}
    if(dp[L][R]!=-1){
        return;
    }

    dp[L][R]=INF;way[L][R]=0;
    if(s[L]==s[R]){
        dfs(L+1,R-1);
        dp[L][R]=dp[L+1][R-1];
        way[L][R]+=way[L+1][R-1];return;
    }

    dfs(L+1,R);dp[L][R]=min(dp[L][R],dp[L+1][R]+1);
    dfs(L,R-1);dp[L][R]=min(dp[L][R],dp[L][R-1]+1);


    if(dp[L][R]==dp[L+1][R]+1) way[L][R]+=way[L+1][R];
    if(dp[L][R]==dp[L][R-1]+1) way[L][R]+=way[L][R-1];
    if(way[L][R]>k) way[L][R]=k+1;

    //printf("L:%d R:%d dp:%d way:%d\n",L,R,dp[L][R],way[L][R]);
    return;
}

char ans[maxn<<1];
int ql,qr;

void print(int L,int R,LL k){
    if(L>R){
        return;
    }
    if(L==R) {ans[ql]=s[L];return;}
    if(s[L]==s[R]){
        ans[ql++]=s[L];ans[qr--]=s[R];
        print(L+1,R-1,k);return;
    }

    if(dp[L+1][R]+1==dp[L][R]&&dp[L][R]!=dp[L][R-1]+1){
        ans[qr--]=s[L];ans[ql++]=s[L];print(L+1,R,k);return;
    }
    else if(dp[L][R]==dp[L][R-1]+1&&dp[L+1][R]+1!=dp[L][R]){
        ans[ql++]=s[R];ans[qr--]=s[R];print(L,R-1,k);return;
    }
    else{
        if(s[L]<s[R]){
            if(way[L+1][R]>=k){
                ans[qr--]=s[L];ans[ql++]=s[L];print(L+1,R,k);return;
            }
            else{
                ans[ql++]=s[R];ans[qr--]=s[R];print(L,R-1,k-way[L+1][R]);return;
            }
        }
        else{
            if(way[L][R-1]>=k){
                ans[ql++]=s[R];ans[qr--]=s[R];print(L,R-1,k);return;
            }
            else{
                ans[qr--]=s[L];ans[ql++]=s[L];print(L+1,R,k-way[L][R-1]);return;
            }
        }
    }
}

int main()
{

    //freopen("C.in","r",stdin);
    scanf("%s",s);n=strlen(s);
    scanf("%lld",&k);

    memset(dp,-1,sizeof(dp));
    dfs(0,n-1);

    ql=0;qr=dp[0][n-1]-1+n;
    if(k>way[0][n-1]) {puts("NONE");return 0;}
    print(0,n-1,k);
    ans[dp[0][n-1]+n]='\0';
    puts(ans);
	return 0;
}
### Prompt

In CPP, your task is to solve the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <iostream>
#include<math.h>
#include<vector>
# include<string.h>
#include <queue>
#include <cstdio>
using namespace std;
const int maxn=2010;
const int INF=10000;
typedef long long LL;
int dp[maxn][maxn];
LL way[maxn][maxn];
int n;
LL k;
char s[maxn];

void dfs(int L,int R){
    if(L>=R) {dp[L][R]=0;way[L][R]=1;return;}
    if(dp[L][R]!=-1){
        return;
    }

    dp[L][R]=INF;way[L][R]=0;
    if(s[L]==s[R]){
        dfs(L+1,R-1);
        dp[L][R]=dp[L+1][R-1];
        way[L][R]+=way[L+1][R-1];return;
    }

    dfs(L+1,R);dp[L][R]=min(dp[L][R],dp[L+1][R]+1);
    dfs(L,R-1);dp[L][R]=min(dp[L][R],dp[L][R-1]+1);


    if(dp[L][R]==dp[L+1][R]+1) way[L][R]+=way[L+1][R];
    if(dp[L][R]==dp[L][R-1]+1) way[L][R]+=way[L][R-1];
    if(way[L][R]>k) way[L][R]=k+1;

    //printf("L:%d R:%d dp:%d way:%d\n",L,R,dp[L][R],way[L][R]);
    return;
}

char ans[maxn<<1];
int ql,qr;

void print(int L,int R,LL k){
    if(L>R){
        return;
    }
    if(L==R) {ans[ql]=s[L];return;}
    if(s[L]==s[R]){
        ans[ql++]=s[L];ans[qr--]=s[R];
        print(L+1,R-1,k);return;
    }

    if(dp[L+1][R]+1==dp[L][R]&&dp[L][R]!=dp[L][R-1]+1){
        ans[qr--]=s[L];ans[ql++]=s[L];print(L+1,R,k);return;
    }
    else if(dp[L][R]==dp[L][R-1]+1&&dp[L+1][R]+1!=dp[L][R]){
        ans[ql++]=s[R];ans[qr--]=s[R];print(L,R-1,k);return;
    }
    else{
        if(s[L]<s[R]){
            if(way[L+1][R]>=k){
                ans[qr--]=s[L];ans[ql++]=s[L];print(L+1,R,k);return;
            }
            else{
                ans[ql++]=s[R];ans[qr--]=s[R];print(L,R-1,k-way[L+1][R]);return;
            }
        }
        else{
            if(way[L][R-1]>=k){
                ans[ql++]=s[R];ans[qr--]=s[R];print(L,R-1,k);return;
            }
            else{
                ans[qr--]=s[L];ans[ql++]=s[L];print(L+1,R,k-way[L][R-1]);return;
            }
        }
    }
}

int main()
{

    //freopen("C.in","r",stdin);
    scanf("%s",s);n=strlen(s);
    scanf("%lld",&k);

    memset(dp,-1,sizeof(dp));
    dfs(0,n-1);

    ql=0;qr=dp[0][n-1]-1+n;
    if(k>way[0][n-1]) {puts("NONE");return 0;}
    print(0,n-1,k);
    ans[dp[0][n-1]+n]='\0';
    puts(ans);
	return 0;
}
```