//
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
#define int long long
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
char s[2010];
char ans[4010];
int n,k;
int l,r,lp,rp;
struct Node{
	int l,s; //least,step
	void add(const Node&b){
		if(b.l+2<l)l=b.l+2,s=b.s;
		else if(b.l+2==l)s=min(s+b.s,k+1);
	}
}dp[2010][2010];
void read(){
	scanf("%s",s);
	cin>>k;
	n=strlen(s);
}
void init(){
	for(int i=0;i<n;i++)dp[i][i].l=dp[i][i].s=1;
	for(int i=1;i<=n;i++)dp[i][i-1].s=1;
	for(int i=1;i<n;i++)
		for(int j=0;j+i<n;j++){
			dp[j][j+i].l=INF;
			if(s[j]==s[j+i])dp[j][j+i].add(dp[j+1][j+i-1]);
			else{
				dp[j][j+i].add(dp[j+1][j+i]);
				dp[j][j+i].add(dp[j][j+i-1]);
			}
		}
}
void solve(){
	if(dp[0][n-1].s<k){
		puts("NONE");
		return;
	}
	r=n-1,rp=dp[0][n-1].l-1;
	while(l<=r){
		if(s[l]==s[r]){
			ans[lp++]=ans[rp--]=s[l];
			l++,r--;
		}else if(s[l]<s[r]){
			if(dp[l+1][r].l+2==dp[l][r].l)
				if(dp[l+1][r].s<k){
					k-=dp[l+1][r].s;
					ans[lp++]=ans[rp--]=s[r--];
				}else ans[lp++]=ans[rp--]=s[l++];
			else ans[lp++]=ans[rp--]=s[r--];
		}else
			if(dp[l][r-1].l+2==dp[l][r].l)
				if(dp[l][r-1].s<k){
					k-=dp[l][r-1].s;
					ans[lp++]=ans[rp--]=s[l++];
				}else ans[lp++]=ans[rp--]=s[r--];
			else ans[lp++]=ans[rp--]=s[l++];
	}
	cout<<ans<<endl;
}
signed main(){
	read();
	init();
	solve();
	return 0;
}


### Prompt

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

Example

Input

crc
1


Output

crc

### Response

```cpp
//
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
#define int long long
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
char s[2010];
char ans[4010];
int n,k;
int l,r,lp,rp;
struct Node{
	int l,s; //least,step
	void add(const Node&b){
		if(b.l+2<l)l=b.l+2,s=b.s;
		else if(b.l+2==l)s=min(s+b.s,k+1);
	}
}dp[2010][2010];
void read(){
	scanf("%s",s);
	cin>>k;
	n=strlen(s);
}
void init(){
	for(int i=0;i<n;i++)dp[i][i].l=dp[i][i].s=1;
	for(int i=1;i<=n;i++)dp[i][i-1].s=1;
	for(int i=1;i<n;i++)
		for(int j=0;j+i<n;j++){
			dp[j][j+i].l=INF;
			if(s[j]==s[j+i])dp[j][j+i].add(dp[j+1][j+i-1]);
			else{
				dp[j][j+i].add(dp[j+1][j+i]);
				dp[j][j+i].add(dp[j][j+i-1]);
			}
		}
}
void solve(){
	if(dp[0][n-1].s<k){
		puts("NONE");
		return;
	}
	r=n-1,rp=dp[0][n-1].l-1;
	while(l<=r){
		if(s[l]==s[r]){
			ans[lp++]=ans[rp--]=s[l];
			l++,r--;
		}else if(s[l]<s[r]){
			if(dp[l+1][r].l+2==dp[l][r].l)
				if(dp[l+1][r].s<k){
					k-=dp[l+1][r].s;
					ans[lp++]=ans[rp--]=s[r--];
				}else ans[lp++]=ans[rp--]=s[l++];
			else ans[lp++]=ans[rp--]=s[r--];
		}else
			if(dp[l][r-1].l+2==dp[l][r].l)
				if(dp[l][r-1].s<k){
					k-=dp[l][r-1].s;
					ans[lp++]=ans[rp--]=s[l++];
				}else ans[lp++]=ans[rp--]=s[r--];
			else ans[lp++]=ans[rp--]=s[l++];
	}
	cout<<ans<<endl;
}
signed main(){
	read();
	init();
	solve();
	return 0;
}


```