#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll INF = 1e18;

pll dp[2005][2005];
string S;
pll dfs(int l, int r){
	pll ret;
	if( dp[l][r] != pll(-INF,-INF) ) return dp[l][r];
	if( r-l <= 0 ) return dp[l][r] = pll(0,1);
	if( S[l] == S[r] ){
		ret = dfs(l+1, r-1);
	}else{
		auto r1 = dfs(l+1, r);
		auto r2 = dfs(l, r-1);
		if( r1.first != r2.first ){
			ret = min( r1, r2 );
		}else{
			ret = pll( r1.first, min(INF, r1.second+r2.second) );
		}
		ret.first++;
	}
	return dp[l][r] = ret;
}

bool flag = false;
string dfs(int l, int r, ll k){
	if( r-l <= 0 && k > 0 ) flag = true;
	if( r-l <= 0 ) return S.substr(l,1+r-l);
	bool sw = true;
	if( S[l] == S[r] ){
		return S[l] + dfs(l+1, r-1, k) + S[l];
	}else{
		auto pl = dfs(l+1, r);
		auto pr = dfs(l, r-1);
		if( pl.first != pr.first ){
			sw = (pl.first < pr.first);
		}else{
			if( S[l] > S[r] ) swap(pl, pr);
			sw = ( S[l] > S[r] ) ^ ( k < pl.second );
			if( k >= pl.second ) k -= pl.second;
		}
	}
	if( sw ) return S[l] + dfs(l+1, r, k) + S[l];
	else     return S[r] + dfs(l, r-1, k) + S[r];
}

int main(){
	ll k;
	cin >> S >> k;
	rep(i,2005) rep(j,2005) dp[i][j] = pll(-INF, -INF);

	auto ans = dfs(0, S.length()-1, k-1);
	cout << (flag ? "NONE" : ans) << endl;

	return 0;
}
### Prompt

Create a solution in CPP for the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll INF = 1e18;

pll dp[2005][2005];
string S;
pll dfs(int l, int r){
	pll ret;
	if( dp[l][r] != pll(-INF,-INF) ) return dp[l][r];
	if( r-l <= 0 ) return dp[l][r] = pll(0,1);
	if( S[l] == S[r] ){
		ret = dfs(l+1, r-1);
	}else{
		auto r1 = dfs(l+1, r);
		auto r2 = dfs(l, r-1);
		if( r1.first != r2.first ){
			ret = min( r1, r2 );
		}else{
			ret = pll( r1.first, min(INF, r1.second+r2.second) );
		}
		ret.first++;
	}
	return dp[l][r] = ret;
}

bool flag = false;
string dfs(int l, int r, ll k){
	if( r-l <= 0 && k > 0 ) flag = true;
	if( r-l <= 0 ) return S.substr(l,1+r-l);
	bool sw = true;
	if( S[l] == S[r] ){
		return S[l] + dfs(l+1, r-1, k) + S[l];
	}else{
		auto pl = dfs(l+1, r);
		auto pr = dfs(l, r-1);
		if( pl.first != pr.first ){
			sw = (pl.first < pr.first);
		}else{
			if( S[l] > S[r] ) swap(pl, pr);
			sw = ( S[l] > S[r] ) ^ ( k < pl.second );
			if( k >= pl.second ) k -= pl.second;
		}
	}
	if( sw ) return S[l] + dfs(l+1, r, k) + S[l];
	else     return S[r] + dfs(l, r-1, k) + S[r];
}

int main(){
	ll k;
	cin >> S >> k;
	rep(i,2005) rep(j,2005) dp[i][j] = pll(-INF, -INF);

	auto ans = dfs(0, S.length()-1, k-1);
	cout << (flag ? "NONE" : ans) << endl;

	return 0;
}
```