#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=2e18;
char s[2005];
ll f[2005][2005],g[2005][2005],k;
bool vis[2005][2005];
ll update(ll a,ll b)
{
	if (a==INF || b==INF) return INF;
	if (a+b>INF) return INF;
	return a+b;
}
void solve(int i,int j)
{
	if (i==j)
	{
		f[i][j]=1,g[i][j]=1;
		return;
	}
	if (i>j)
	{
		f[i][j]=0,g[i][j]=1;
		return;
	}
	if (vis[i][j]) return;
	vis[i][j]=true;
	if (s[i]==s[j])
	{
		solve(i+1,j-1);
		f[i][j]=f[i+1][j-1]+2,g[i][j]=g[i+1][j-1];
	}
	else
	{
		solve(i+1,j);
		solve(i,j-1);
		f[i][j]=min(f[i+1][j],f[i][j-1])+2;
		if (f[i+1][j]==f[i][j-1]) g[i][j]=update(g[i+1][j],g[i][j-1]);
		else if (f[i+1][j]<f[i][j-1]) g[i][j]=g[i+1][j];
		else g[i][j]=g[i][j-1];
	}
} 
void get_ans()
{
	int len=strlen(s);
	if (k>g[0][len-1])
	{
		printf("NONE\n");
		return;
	}
	int tot=f[0][len-1];
	int p=0,q=len-1;
	string ans="";
	while (p<=q)
	{
		if (s[p]==s[q]) ans+=s[p],p++,q--;
		else
		{
			if (f[p+1][q]==f[p][q-1])
			{
				if (s[p]>s[q])
				{
					if (k>g[p][q-1])
						k-=g[p][q-1],ans+=s[p],p++;
					else
						ans+=s[q],q--;
				}
				else
				{
					if (k>g[p+1][q])
						k-=g[p+1][q],ans+=s[q],q--;
					else
						ans+=s[p],p++;
				}
			}
			else if (f[p+1][q]<f[p][q-1])
				ans+=s[p],p++;
			else ans+=s[q],q--;
		}
	}
	cout<<ans;
	reverse(ans.begin(),ans.end());
	if (tot%2) ans=ans.substr(1);
	cout<<ans<<endl;
}
int main()
{
	scanf("%s",s);
	scanf("%lld",&k);
	int len=strlen(s);
	solve(0,len-1);
	get_ans();
	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>
using namespace std;
typedef long long ll;
const ll INF=2e18;
char s[2005];
ll f[2005][2005],g[2005][2005],k;
bool vis[2005][2005];
ll update(ll a,ll b)
{
	if (a==INF || b==INF) return INF;
	if (a+b>INF) return INF;
	return a+b;
}
void solve(int i,int j)
{
	if (i==j)
	{
		f[i][j]=1,g[i][j]=1;
		return;
	}
	if (i>j)
	{
		f[i][j]=0,g[i][j]=1;
		return;
	}
	if (vis[i][j]) return;
	vis[i][j]=true;
	if (s[i]==s[j])
	{
		solve(i+1,j-1);
		f[i][j]=f[i+1][j-1]+2,g[i][j]=g[i+1][j-1];
	}
	else
	{
		solve(i+1,j);
		solve(i,j-1);
		f[i][j]=min(f[i+1][j],f[i][j-1])+2;
		if (f[i+1][j]==f[i][j-1]) g[i][j]=update(g[i+1][j],g[i][j-1]);
		else if (f[i+1][j]<f[i][j-1]) g[i][j]=g[i+1][j];
		else g[i][j]=g[i][j-1];
	}
} 
void get_ans()
{
	int len=strlen(s);
	if (k>g[0][len-1])
	{
		printf("NONE\n");
		return;
	}
	int tot=f[0][len-1];
	int p=0,q=len-1;
	string ans="";
	while (p<=q)
	{
		if (s[p]==s[q]) ans+=s[p],p++,q--;
		else
		{
			if (f[p+1][q]==f[p][q-1])
			{
				if (s[p]>s[q])
				{
					if (k>g[p][q-1])
						k-=g[p][q-1],ans+=s[p],p++;
					else
						ans+=s[q],q--;
				}
				else
				{
					if (k>g[p+1][q])
						k-=g[p+1][q],ans+=s[q],q--;
					else
						ans+=s[p],p++;
				}
			}
			else if (f[p+1][q]<f[p][q-1])
				ans+=s[p],p++;
			else ans+=s[q],q--;
		}
	}
	cout<<ans;
	reverse(ans.begin(),ans.end());
	if (tot%2) ans=ans.substr(1);
	cout<<ans<<endl;
}
int main()
{
	scanf("%s",s);
	scanf("%lld",&k);
	int len=strlen(s);
	solve(0,len-1);
	get_ans();
	return 0;
}

```