#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <complex>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define REP(i, n) for(int i=0;i<(int)n;i++)
#define REPS(i, n) for(int i=1;i<=(int)n;i++)
#define RREP(i, n) for(int i=n-1;i>=0;i--)
#define RREPS(i, n) for(int i=n;i>0;i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define pb push_back
#define eb emplace_back
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

string s;
ll k;
string ans;
string ansrev;

ll memo[2001][2001];
ll mini[2001][2001];

ll minimum(int l, int r){
	ll &res = mini[l][r];
	if(res >= 0) return res;
	if(r <= l) return res = 0;
	if(l+1 == r) return res = 1;
	if(s[l] == s[r-1]) return res = minimum(l+1, r-1) + 2;
	return res = min(minimum(l+1, r), minimum(l, r-1)) + 2;
}

ll count(int l, int r){
	ll &res = memo[l][r];
	if(res >= 0) return res;
	if(r <= l) return res = 1;
	if(s[l] == s[r-1]) return res = count(l+1, r-1);
	ll mi = min(minimum(l+1, r), minimum(l, r-1));
	res = 0;
	if(minimum(l+1, r) == mi) res += count(l+1, r);
	if(minimum(l, r-1) == mi) res += count(l, r-1);
	if(res > 1e18 + 10) res = 1e18 + 10;
	return res;
}

void dfs(int l, int r, ll k){
	if(l == r){
		reverse(ALL(ansrev));
		if(k) cout << "NONE" << endl;
		else cout << ans << ansrev << endl;
	}else if(l+1 == r){
		ans.pb(s[l]);
		dfs(l+1, r, k);
	}else if(s[l] == s[r-1]){
		ans.pb(s[l]);
		ansrev.pb(s[l]);
		dfs(l+1, r-1, k);
	}else{
		ll minl = minimum(l+1, r);
		ll minr = minimum(l, r-1);
		if(minr < minl){
			ans.pb(s[r-1]);
			ansrev.pb(s[r-1]);
			dfs(l, r-1, k);
		}else if(minl < minr){
			ans.pb(s[l]);
			ansrev.pb(s[l]);
			dfs(l+1, r, k);
		}else if(s[l] < s[r-1]){ // x[...]y
			ll res = count(l+1, r);
			if(k < res){
				ans.pb(s[l]);
				ansrev.pb(s[l]);
				dfs(l+1, r, k);
			}else{
				ans.pb(s[r-1]);
				ansrev.pb(s[r-1]);
				dfs(l, r-1, k - res);
			}
		}else{ // y[...]x
			ll res = count(l, r-1);
			if(k < res){
				ans.pb(s[r-1]);
				ansrev.pb(s[r-1]);
				dfs(l, r-1, k);
			}else{
				ans.pb(s[l]);
				ansrev.pb(s[l]);
				dfs(l+1, r, k - res);
			}
		}
	}
}
int main(){
	cin >> s >> k;
	memset(memo, -1, sizeof(memo));
	memset(mini, -1, sizeof(mini));
	dfs(0, s.size(), k - 1);
	return 0;
}
### Prompt

Develop a solution in CPP to the problem described below:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <complex>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define REP(i, n) for(int i=0;i<(int)n;i++)
#define REPS(i, n) for(int i=1;i<=(int)n;i++)
#define RREP(i, n) for(int i=n-1;i>=0;i--)
#define RREPS(i, n) for(int i=n;i>0;i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define pb push_back
#define eb emplace_back
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

string s;
ll k;
string ans;
string ansrev;

ll memo[2001][2001];
ll mini[2001][2001];

ll minimum(int l, int r){
	ll &res = mini[l][r];
	if(res >= 0) return res;
	if(r <= l) return res = 0;
	if(l+1 == r) return res = 1;
	if(s[l] == s[r-1]) return res = minimum(l+1, r-1) + 2;
	return res = min(minimum(l+1, r), minimum(l, r-1)) + 2;
}

ll count(int l, int r){
	ll &res = memo[l][r];
	if(res >= 0) return res;
	if(r <= l) return res = 1;
	if(s[l] == s[r-1]) return res = count(l+1, r-1);
	ll mi = min(minimum(l+1, r), minimum(l, r-1));
	res = 0;
	if(minimum(l+1, r) == mi) res += count(l+1, r);
	if(minimum(l, r-1) == mi) res += count(l, r-1);
	if(res > 1e18 + 10) res = 1e18 + 10;
	return res;
}

void dfs(int l, int r, ll k){
	if(l == r){
		reverse(ALL(ansrev));
		if(k) cout << "NONE" << endl;
		else cout << ans << ansrev << endl;
	}else if(l+1 == r){
		ans.pb(s[l]);
		dfs(l+1, r, k);
	}else if(s[l] == s[r-1]){
		ans.pb(s[l]);
		ansrev.pb(s[l]);
		dfs(l+1, r-1, k);
	}else{
		ll minl = minimum(l+1, r);
		ll minr = minimum(l, r-1);
		if(minr < minl){
			ans.pb(s[r-1]);
			ansrev.pb(s[r-1]);
			dfs(l, r-1, k);
		}else if(minl < minr){
			ans.pb(s[l]);
			ansrev.pb(s[l]);
			dfs(l+1, r, k);
		}else if(s[l] < s[r-1]){ // x[...]y
			ll res = count(l+1, r);
			if(k < res){
				ans.pb(s[l]);
				ansrev.pb(s[l]);
				dfs(l+1, r, k);
			}else{
				ans.pb(s[r-1]);
				ansrev.pb(s[r-1]);
				dfs(l, r-1, k - res);
			}
		}else{ // y[...]x
			ll res = count(l, r-1);
			if(k < res){
				ans.pb(s[r-1]);
				ansrev.pb(s[r-1]);
				dfs(l, r-1, k);
			}else{
				ans.pb(s[l]);
				ansrev.pb(s[l]);
				dfs(l+1, r, k - res);
			}
		}
	}
}
int main(){
	cin >> s >> k;
	memset(memo, -1, sizeof(memo));
	memset(mini, -1, sizeof(mini));
	dfs(0, s.size(), k - 1);
	return 0;
}
```