//#include <bits / stdc++.h>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
#define Maxl (5000)
#define LL long long
#define inf (0X7fffffff/2)

LL K;
int len,nl,nr;
char st[Maxl],ans[Maxl];
int dp[Maxl][Maxl];
LL cnt[Maxl][Maxl];
void dfs(int l,int r){
	if (dp[l][r]!=0) return;
	dp[l][r]=inf;
	cnt[l][r]=0;
	if (l>=r)
	{
		dp[l][r]=(l==r);
		cnt[l][r]=1;
		return;
	}
	if (st[l]==st[r])
	{
		dfs(l+1,r-1);
		dp[l][r]=dp[l+1][r-1]+2;
		cnt[l][r]=cnt[l+1][r-1];
		return;
	}
	
	dfs(l+1,r);
	dfs(l,r-1);
	dp[l][r]=min(dp[l+1][r]+2,dp[l][r-1]+2);

	if (dp[l][r]==dp[l+1][r]+2) cnt[l][r]+=cnt[l+1][r];
	if (dp[l][r]==dp[l][r-1]+2) cnt[l][r]+=cnt[l][r-1];
	if (cnt[l][r]>K) cnt[l][r]=K+1;
}
void getans(int l,int r,LL Now){
	if (l>=r)
	{
		if (l==r) ans[nl++]=st[l];
		return;
	}
	if (st[l]==st[r])
	{
		ans[nl++]=st[l];
		ans[nr--]=st[r];
		getans(l+1,r-1,Now);
		return;
	}
	if (dp[l][r]==dp[l+1][r]+2&&dp[l][r]!=dp[l][r-1]+2)
	{
		ans[nl++]=st[l];ans[nr--]=st[l];
		getans(l+1,r,Now);
		return;
	}
	if (dp[l][r]!=dp[l+1][r]+2&&dp[l][r]==dp[l][r-1]+2)
	{
		ans[nl++]=st[r];ans[nr--]=st[r];
		getans(l,r-1,Now);
		return;
	}
	if (st[l]<st[r])
	{
		if (Now<=cnt[l+1][r])
		{
			ans[nl++]=st[l];ans[nr--]=st[l];
			getans(l+1,r,Now);
		}
		else
		{
			ans[nl++]=st[r];ans[nr--]=st[r];
			getans(l,r-1,Now-cnt[l+1][r]);
		}
	}
	else
	{
		if (Now<=cnt[l][r-1])
		{
			ans[nl++]=st[r];ans[nr--]=st[r];
			getans(l,r-1,Now);
		}
		else
		{
			ans[nl++]=st[l];ans[nr--]=st[l];
			getans(l+1,r,Now-cnt[l][r-1]);
		}
	}
}
int main(){
	scanf("%s",st+1);
	scanf("%lld",&K);
	len=strlen(st+1);
	dfs(1,len);	if (cnt[1][len]<K)
	{
		printf("NONE\n");
	}
	else
	{
		nl=1;nr=dp[1][len];
		getans(1,len,K);
		printf("%s\n",ans+1);
	}
	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>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
#define Maxl (5000)
#define LL long long
#define inf (0X7fffffff/2)

LL K;
int len,nl,nr;
char st[Maxl],ans[Maxl];
int dp[Maxl][Maxl];
LL cnt[Maxl][Maxl];
void dfs(int l,int r){
	if (dp[l][r]!=0) return;
	dp[l][r]=inf;
	cnt[l][r]=0;
	if (l>=r)
	{
		dp[l][r]=(l==r);
		cnt[l][r]=1;
		return;
	}
	if (st[l]==st[r])
	{
		dfs(l+1,r-1);
		dp[l][r]=dp[l+1][r-1]+2;
		cnt[l][r]=cnt[l+1][r-1];
		return;
	}
	
	dfs(l+1,r);
	dfs(l,r-1);
	dp[l][r]=min(dp[l+1][r]+2,dp[l][r-1]+2);

	if (dp[l][r]==dp[l+1][r]+2) cnt[l][r]+=cnt[l+1][r];
	if (dp[l][r]==dp[l][r-1]+2) cnt[l][r]+=cnt[l][r-1];
	if (cnt[l][r]>K) cnt[l][r]=K+1;
}
void getans(int l,int r,LL Now){
	if (l>=r)
	{
		if (l==r) ans[nl++]=st[l];
		return;
	}
	if (st[l]==st[r])
	{
		ans[nl++]=st[l];
		ans[nr--]=st[r];
		getans(l+1,r-1,Now);
		return;
	}
	if (dp[l][r]==dp[l+1][r]+2&&dp[l][r]!=dp[l][r-1]+2)
	{
		ans[nl++]=st[l];ans[nr--]=st[l];
		getans(l+1,r,Now);
		return;
	}
	if (dp[l][r]!=dp[l+1][r]+2&&dp[l][r]==dp[l][r-1]+2)
	{
		ans[nl++]=st[r];ans[nr--]=st[r];
		getans(l,r-1,Now);
		return;
	}
	if (st[l]<st[r])
	{
		if (Now<=cnt[l+1][r])
		{
			ans[nl++]=st[l];ans[nr--]=st[l];
			getans(l+1,r,Now);
		}
		else
		{
			ans[nl++]=st[r];ans[nr--]=st[r];
			getans(l,r-1,Now-cnt[l+1][r]);
		}
	}
	else
	{
		if (Now<=cnt[l][r-1])
		{
			ans[nl++]=st[r];ans[nr--]=st[r];
			getans(l,r-1,Now);
		}
		else
		{
			ans[nl++]=st[l];ans[nr--]=st[l];
			getans(l+1,r,Now-cnt[l][r-1]);
		}
	}
}
int main(){
	scanf("%s",st+1);
	scanf("%lld",&K);
	len=strlen(st+1);
	dfs(1,len);	if (cnt[1][len]<K)
	{
		printf("NONE\n");
	}
	else
	{
		nl=1;nr=dp[1][len];
		getans(1,len,K);
		printf("%s\n",ans+1);
	}
	return 0;
}
```