//Original Code:
//#include <self/utility>
//#include <self/debug>
//using namespace std;
//string s;
//ll k;
//pair<int,ll> dp[2005][2005];
//int n;
//char c[4005];
//
//pair<int,ll> dfs(int l,int r)
//{
//	if(dp[l][r]!=mp(-1,-1LL)) return dp[l][r];
//	pair<int,ll> &res=dp[l][r];
//	if(l==r) return res=mp(1,1);
//	if(l+1==r && s[l]==s[r]) return res=mp(2,1);
//	if(s[l]==s[r]) return res=dfs(l+1,r-1)+mp(2,0LL);
//	pair<int,ll> o1=dfs(l+1,r)+mp(2,0LL),o2=dfs(l,r-1)+mp(2,0LL);
//	if(o1.first==o2.first) return res=mp(o1.first,min(o1.second+o2.second,llinf));
//	else return res=min(o1,o2);
//}
//
//void solve(int l,int r,int pl,int pr,ll k)
//{
////	cout<<pl<<' '<<pr<<endl;
////	assert(k<dp[l][r].second);
//	if(l==r)
//	{
//		c[pl]=s[l];
//		return;
//	}
//	if(l>r) return;
//	if(s[l]==s[r])
//	{
//		c[pl]=s[l];
//		c[pr]=s[r];
//		solve(l+1,r-1,pl+1,pr-1,k);
//		return;
//	}
//	pair<int,ll> o1=dfs(l+1,r)+mp(2,0LL),o2=dfs(l,r-1)+mp(2,0LL);
//	if(o1.first>o2.first)
//	{
//		c[pl++]=s[r];
//		c[pr--]=s[r];
//		solve(l,r-1,pl,pr,k);
//	}
//	else if(o1.first<o2.first)
//	{
//		c[pl++]=s[l];
//		c[pr--]=s[l];
//		solve(l+1,r,pl,pr,k);
//	}
//	else
//	{
//		ll partSmall,partBig;
//		int lSmall,rSmall;
//		int lBig,rBig;
//		char chSmall,chBig;
//		lSmall=l;
//		rSmall=r-1;
//		lBig=l+1;
//		rBig=r;
//		chSmall=s[r];
//		chBig=s[l];
//		if(s[l]<s[r])
//		{
//			swap(lSmall,lBig);
//			swap(rSmall,rBig);
//			swap(chSmall,chBig);
//		}
//		partSmall=dp[lSmall][rSmall].second;
//		partBig=dp[lBig][rBig].second;
//		if(k>=partSmall)
//		{
//			c[pl++]=chBig;
//			c[pr--]=chBig;
//			solve(lBig,rBig,pl,pr,k-partSmall);
//		}
//		else
//		{
//			c[pl++]=chSmall;
//			c[pr--]=chSmall;
//			solve(lSmall,rSmall,pl,pr,k);
//		}
//	}
//}
//
//int main()
//{
////	freopen("input.txt","r",stdin);
//	cin>>s>>k;
//	memset(dp,-1,sizeof(dp));
//	n=s.size();
//	dfs(0,n-1);
//	k--;
//	if(k>=dp[0][n-1].second) over("NONE");
//	solve(0,n-1,0,dp[0][n-1].first-1,k);
//	for(int i=0;i<dp[0][n-1].first;i++)
//	{
//		putchar(c[i]);
//	}
//	puts("");
//	return 0;
//}

//substituted with C++ Inliner
#ifndef _SELF_UTILITY
#define _SELF_UTILITY 1
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#define Endl endl
#define mp make_pair
#define ll long long 
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define quickcin ios_base::sync_with_stdio(false);
const int mod=200003;
const int gmod=2;
const int inf=1039074182;
const ll llinf=1LL*inf*inf;
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;}
template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;}
template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;}
#endif

#ifndef _SELF_DEBUG
#define _SELF_DEBUG 1
#ifndef _SELF_OPERATOR
#define _SELF_OPERATOR 1
using namespace std;
template <typename T>
ostream & operator << (ostream& cout,vector<T> vec)
{
	cout<<"{";
	for(int i=0;i<vec.size();i++)
	{
		cout<<vec[i];
		if(i!=(int)vec.size()-1) cout<<',';
	}
	cout<<"}";
	return cout;
}

template <typename T1,typename T2>
ostream & operator << (ostream & cout,pair<T1,T2> p)
{
	cout<<"("<<p.first<<','<<p.second<<")";
	return cout;
}

template <typename T>
ostream & operator << (ostream & cout,set <T> s)
{
	vector <T> t;
	for(auto x:s) t.push_back(x);
	cout<<t;
	return cout;
}

template <typename T>
ostream & operator << (ostream &cout,queue <T> q)
{
	vector <T> t;
	while(q.size())
	{
		t.push_back(q.front());
		q.pop();
	}
	cout<<t;
	return cout;
}

template <typename T1,typename T2>
ostream & operator << (ostream &cout,map <T1,T2> m)
{
	for(auto &x:m)
	{
		cout<<"Key: "<<x.first<<' '<<"Value: "<<x.second<<endl;
	}
	return cout;
}

template <typename T>
T operator * (vector <T> v1,vector <T> v2)
{
	assert(v1.size()==v2.size());
	int n=v1.size();
	T res=0;
	for(int i=0;i<n;i++)
	{
		res+=v1[i]*v2[i];
	}
	return res;
}

template <typename T1,typename T2>
pair<T1,T2> operator + (pair<T1,T2> x,pair<T1,T2> y)
{
	return make_pair(x.first+y.first,x.second+y.second);
}

template <typename T1,typename T2>
pair<T1,T2> operator - (pair<T1,T2> x)
{
	return make_pair(-x.first,-x.second);
}

template <typename T>
vector<vector<T> > operator ~ (vector<vector <T> > vec)
{
	vector <vector<T> > v;
	int n=vec.size(),m=vec[0].size();
	v.resize(m);
	for(int i=0;i<m;i++)
	{
		v[i].resize(n);
	}
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			v[i][j]=vec[j][i];
		}
	}
	return v;
}
#endif

void print0x(int x)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	std::reverse(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}

template <typename T>
void print0x(T x,int len)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	reverse(vec.begin(),vec.end());
	for(int i=vec.size();i<len;i++)
	{
		putchar('0');
	}
	for(int i=0;i<vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}
#endif
using namespace std;
string s;
ll k;
pair<int,ll> dp[2005][2005];
int n;
char c[4005];

pair<int,ll> dfs(int l,int r)
{
	if(dp[l][r]!=mp(-1,-1LL)) return dp[l][r];
	pair<int,ll> &res=dp[l][r];
	if(l==r) return res=mp(1,1);
	if(l+1==r && s[l]==s[r]) return res=mp(2,1);
	if(s[l]==s[r]) return res=dfs(l+1,r-1)+mp(2,0LL);
	pair<int,ll> o1=dfs(l+1,r)+mp(2,0LL),o2=dfs(l,r-1)+mp(2,0LL);
	if(o1.first==o2.first) return res=mp(o1.first,min(o1.second+o2.second,llinf));
	else return res=min(o1,o2);
}

void solve(int l,int r,int pl,int pr,ll k)
{
//	cout<<pl<<' '<<pr<<endl;
//	assert(k<dp[l][r].second);
	if(l==r)
	{
		c[pl]=s[l];
		return;
	}
	if(l>r) return;
	if(s[l]==s[r])
	{
		c[pl]=s[l];
		c[pr]=s[r];
		solve(l+1,r-1,pl+1,pr-1,k);
		return;
	}
	pair<int,ll> o1=dfs(l+1,r)+mp(2,0LL),o2=dfs(l,r-1)+mp(2,0LL);
	if(o1.first>o2.first)
	{
		c[pl++]=s[r];
		c[pr--]=s[r];
		solve(l,r-1,pl,pr,k);
	}
	else if(o1.first<o2.first)
	{
		c[pl++]=s[l];
		c[pr--]=s[l];
		solve(l+1,r,pl,pr,k);
	}
	else
	{
		ll partSmall,partBig;
		int lSmall,rSmall;
		int lBig,rBig;
		char chSmall,chBig;
		lSmall=l;
		rSmall=r-1;
		lBig=l+1;
		rBig=r;
		chSmall=s[r];
		chBig=s[l];
		if(s[l]<s[r])
		{
			swap(lSmall,lBig);
			swap(rSmall,rBig);
			swap(chSmall,chBig);
		}
		partSmall=dp[lSmall][rSmall].second;
		partBig=dp[lBig][rBig].second;
		if(k>=partSmall)
		{
			c[pl++]=chBig;
			c[pr--]=chBig;
			solve(lBig,rBig,pl,pr,k-partSmall);
		}
		else
		{
			c[pl++]=chSmall;
			c[pr--]=chSmall;
			solve(lSmall,rSmall,pl,pr,k);
		}
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>s>>k;
	memset(dp,-1,sizeof(dp));
	n=s.size();
	dfs(0,n-1);
	k--;
	if(k>=dp[0][n-1].second) over("NONE");
	solve(0,n-1,0,dp[0][n-1].first-1,k);
	for(int i=0;i<dp[0][n-1].first;i++)
	{
		putchar(c[i]);
	}
	puts("");
	return 0;
}


### Prompt

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

Example

Input

crc
1


Output

crc

### Response

```cpp
//Original Code:
//#include <self/utility>
//#include <self/debug>
//using namespace std;
//string s;
//ll k;
//pair<int,ll> dp[2005][2005];
//int n;
//char c[4005];
//
//pair<int,ll> dfs(int l,int r)
//{
//	if(dp[l][r]!=mp(-1,-1LL)) return dp[l][r];
//	pair<int,ll> &res=dp[l][r];
//	if(l==r) return res=mp(1,1);
//	if(l+1==r && s[l]==s[r]) return res=mp(2,1);
//	if(s[l]==s[r]) return res=dfs(l+1,r-1)+mp(2,0LL);
//	pair<int,ll> o1=dfs(l+1,r)+mp(2,0LL),o2=dfs(l,r-1)+mp(2,0LL);
//	if(o1.first==o2.first) return res=mp(o1.first,min(o1.second+o2.second,llinf));
//	else return res=min(o1,o2);
//}
//
//void solve(int l,int r,int pl,int pr,ll k)
//{
////	cout<<pl<<' '<<pr<<endl;
////	assert(k<dp[l][r].second);
//	if(l==r)
//	{
//		c[pl]=s[l];
//		return;
//	}
//	if(l>r) return;
//	if(s[l]==s[r])
//	{
//		c[pl]=s[l];
//		c[pr]=s[r];
//		solve(l+1,r-1,pl+1,pr-1,k);
//		return;
//	}
//	pair<int,ll> o1=dfs(l+1,r)+mp(2,0LL),o2=dfs(l,r-1)+mp(2,0LL);
//	if(o1.first>o2.first)
//	{
//		c[pl++]=s[r];
//		c[pr--]=s[r];
//		solve(l,r-1,pl,pr,k);
//	}
//	else if(o1.first<o2.first)
//	{
//		c[pl++]=s[l];
//		c[pr--]=s[l];
//		solve(l+1,r,pl,pr,k);
//	}
//	else
//	{
//		ll partSmall,partBig;
//		int lSmall,rSmall;
//		int lBig,rBig;
//		char chSmall,chBig;
//		lSmall=l;
//		rSmall=r-1;
//		lBig=l+1;
//		rBig=r;
//		chSmall=s[r];
//		chBig=s[l];
//		if(s[l]<s[r])
//		{
//			swap(lSmall,lBig);
//			swap(rSmall,rBig);
//			swap(chSmall,chBig);
//		}
//		partSmall=dp[lSmall][rSmall].second;
//		partBig=dp[lBig][rBig].second;
//		if(k>=partSmall)
//		{
//			c[pl++]=chBig;
//			c[pr--]=chBig;
//			solve(lBig,rBig,pl,pr,k-partSmall);
//		}
//		else
//		{
//			c[pl++]=chSmall;
//			c[pr--]=chSmall;
//			solve(lSmall,rSmall,pl,pr,k);
//		}
//	}
//}
//
//int main()
//{
////	freopen("input.txt","r",stdin);
//	cin>>s>>k;
//	memset(dp,-1,sizeof(dp));
//	n=s.size();
//	dfs(0,n-1);
//	k--;
//	if(k>=dp[0][n-1].second) over("NONE");
//	solve(0,n-1,0,dp[0][n-1].first-1,k);
//	for(int i=0;i<dp[0][n-1].first;i++)
//	{
//		putchar(c[i]);
//	}
//	puts("");
//	return 0;
//}

//substituted with C++ Inliner
#ifndef _SELF_UTILITY
#define _SELF_UTILITY 1
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#define Endl endl
#define mp make_pair
#define ll long long 
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define quickcin ios_base::sync_with_stdio(false);
const int mod=200003;
const int gmod=2;
const int inf=1039074182;
const ll llinf=1LL*inf*inf;
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;}
template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;}
template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;}
#endif

#ifndef _SELF_DEBUG
#define _SELF_DEBUG 1
#ifndef _SELF_OPERATOR
#define _SELF_OPERATOR 1
using namespace std;
template <typename T>
ostream & operator << (ostream& cout,vector<T> vec)
{
	cout<<"{";
	for(int i=0;i<vec.size();i++)
	{
		cout<<vec[i];
		if(i!=(int)vec.size()-1) cout<<',';
	}
	cout<<"}";
	return cout;
}

template <typename T1,typename T2>
ostream & operator << (ostream & cout,pair<T1,T2> p)
{
	cout<<"("<<p.first<<','<<p.second<<")";
	return cout;
}

template <typename T>
ostream & operator << (ostream & cout,set <T> s)
{
	vector <T> t;
	for(auto x:s) t.push_back(x);
	cout<<t;
	return cout;
}

template <typename T>
ostream & operator << (ostream &cout,queue <T> q)
{
	vector <T> t;
	while(q.size())
	{
		t.push_back(q.front());
		q.pop();
	}
	cout<<t;
	return cout;
}

template <typename T1,typename T2>
ostream & operator << (ostream &cout,map <T1,T2> m)
{
	for(auto &x:m)
	{
		cout<<"Key: "<<x.first<<' '<<"Value: "<<x.second<<endl;
	}
	return cout;
}

template <typename T>
T operator * (vector <T> v1,vector <T> v2)
{
	assert(v1.size()==v2.size());
	int n=v1.size();
	T res=0;
	for(int i=0;i<n;i++)
	{
		res+=v1[i]*v2[i];
	}
	return res;
}

template <typename T1,typename T2>
pair<T1,T2> operator + (pair<T1,T2> x,pair<T1,T2> y)
{
	return make_pair(x.first+y.first,x.second+y.second);
}

template <typename T1,typename T2>
pair<T1,T2> operator - (pair<T1,T2> x)
{
	return make_pair(-x.first,-x.second);
}

template <typename T>
vector<vector<T> > operator ~ (vector<vector <T> > vec)
{
	vector <vector<T> > v;
	int n=vec.size(),m=vec[0].size();
	v.resize(m);
	for(int i=0;i<m;i++)
	{
		v[i].resize(n);
	}
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			v[i][j]=vec[j][i];
		}
	}
	return v;
}
#endif

void print0x(int x)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	std::reverse(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}

template <typename T>
void print0x(T x,int len)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	reverse(vec.begin(),vec.end());
	for(int i=vec.size();i<len;i++)
	{
		putchar('0');
	}
	for(int i=0;i<vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}
#endif
using namespace std;
string s;
ll k;
pair<int,ll> dp[2005][2005];
int n;
char c[4005];

pair<int,ll> dfs(int l,int r)
{
	if(dp[l][r]!=mp(-1,-1LL)) return dp[l][r];
	pair<int,ll> &res=dp[l][r];
	if(l==r) return res=mp(1,1);
	if(l+1==r && s[l]==s[r]) return res=mp(2,1);
	if(s[l]==s[r]) return res=dfs(l+1,r-1)+mp(2,0LL);
	pair<int,ll> o1=dfs(l+1,r)+mp(2,0LL),o2=dfs(l,r-1)+mp(2,0LL);
	if(o1.first==o2.first) return res=mp(o1.first,min(o1.second+o2.second,llinf));
	else return res=min(o1,o2);
}

void solve(int l,int r,int pl,int pr,ll k)
{
//	cout<<pl<<' '<<pr<<endl;
//	assert(k<dp[l][r].second);
	if(l==r)
	{
		c[pl]=s[l];
		return;
	}
	if(l>r) return;
	if(s[l]==s[r])
	{
		c[pl]=s[l];
		c[pr]=s[r];
		solve(l+1,r-1,pl+1,pr-1,k);
		return;
	}
	pair<int,ll> o1=dfs(l+1,r)+mp(2,0LL),o2=dfs(l,r-1)+mp(2,0LL);
	if(o1.first>o2.first)
	{
		c[pl++]=s[r];
		c[pr--]=s[r];
		solve(l,r-1,pl,pr,k);
	}
	else if(o1.first<o2.first)
	{
		c[pl++]=s[l];
		c[pr--]=s[l];
		solve(l+1,r,pl,pr,k);
	}
	else
	{
		ll partSmall,partBig;
		int lSmall,rSmall;
		int lBig,rBig;
		char chSmall,chBig;
		lSmall=l;
		rSmall=r-1;
		lBig=l+1;
		rBig=r;
		chSmall=s[r];
		chBig=s[l];
		if(s[l]<s[r])
		{
			swap(lSmall,lBig);
			swap(rSmall,rBig);
			swap(chSmall,chBig);
		}
		partSmall=dp[lSmall][rSmall].second;
		partBig=dp[lBig][rBig].second;
		if(k>=partSmall)
		{
			c[pl++]=chBig;
			c[pr--]=chBig;
			solve(lBig,rBig,pl,pr,k-partSmall);
		}
		else
		{
			c[pl++]=chSmall;
			c[pr--]=chSmall;
			solve(lSmall,rSmall,pl,pr,k);
		}
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>s>>k;
	memset(dp,-1,sizeof(dp));
	n=s.size();
	dfs(0,n-1);
	k--;
	if(k>=dp[0][n-1].second) over("NONE");
	solve(0,n-1,0,dp[0][n-1].first-1,k);
	for(int i=0;i<dp[0][n-1].first;i++)
	{
		putchar(c[i]);
	}
	puts("");
	return 0;
}


```