#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

const ll inf = 1LL << 61;
string a, b;
ll k;

ll dp[2010][2010];
ll num[2010][2010];

int main(void) {
	cin >> a >> k;
	b = a; reverse(begin(b), end(b));

	const int n = a.size();

	rep(i, n + 1)rep(j, n + 1) dp[i][j] = inf;

	rep(i, n + 1) {
		dp[i][n] = n - i;
		dp[n][i] = n - i;
	}

	rrep(i, n) rrep(j, n) {
		if (a[i] == b[j]) {
			chmin(dp[i][j], dp[i + 1][j + 1] + 1);
		} else {
			//cerr << i << " " << j << endl;
			chmin(dp[i][j], dp[i + 1][j] + 1);
			chmin(dp[i][j], dp[i][j + 1] + 1);
		}
	}

	rep(i, n + 1)rep(j, n + 1)  if (dp[0][0] / 2 == dp[i][j]) num[i][j] = 1LL;

	rrep(i, n) rrep(j, n) {
		if (i + j > n) continue;
		//cerr << i << " " << j << endl;


		if (a[i] == b[j]) {
			if (dp[i][j] == dp[i + 1][j + 1] + 1) {
				num[i][j] += num[i + 1][j + 1];
			}
		} else {
			if (dp[i][j] == dp[i + 1][j] + 1) {
				num[i][j] += num[i + 1][j];
			}

			if (dp[i][j] == dp[i][j + 1] + 1) {
				num[i][j] += num[i][j + 1];
			}
		}
		chmin(num[i][j], inf);
	}

	/*
	rep(i, n + 1) {
		rep(j, n + 1) cout << dp[i][j] << " ";
		cout << endl;
	}
	

	
	rep(i, n + 1) {
		rep(j, n + 1) cout << num[i][j] << " ";
		cout << endl;
	}
	*/
	
	

	if (num[0][0] < k) {
		puts("NONE");
		return 0;
	}


	string ans = "";
	int ci = 0, cj = 0;

	while (1) {
		if (dp[ci][cj] == dp[0][0] / 2) break;

		if (a[ci] == b[cj]) {
			ans += a[ci];
			ci++, cj++;
			continue;
		}

		if (ci < n and (cj == n or dp[ci][cj] != dp[ci][cj + 1] + 1)) {
			ans += a[ci];
			ci++;
			continue;
		}

		if (cj < n and (ci == n or dp[ci][cj] != dp[ci + 1][cj] + 1)) {
			ans += b[cj];
			cj++;
			continue;
		}


		if (a[ci] < b[cj]) {
			if (k <= num[ci + 1][cj])
				ans += a[ci++];
			else
				k -= num[ci + 1][cj], ans += b[cj++];

		} else {
			//cerr << "Call " << ci << " " << cj  << " " << num[ci][cj + 1] << endl;
			if (k <= num[ci][cj + 1])
				ans += b[cj++];
			else
				k -= num[ci][cj + 1], ans += a[ci++];
		}
	}

	const int rest = dp[0][0] - int(ans.size());
	rrep(i,rest) ans += ans[i];
	cout << 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 _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

const ll inf = 1LL << 61;
string a, b;
ll k;

ll dp[2010][2010];
ll num[2010][2010];

int main(void) {
	cin >> a >> k;
	b = a; reverse(begin(b), end(b));

	const int n = a.size();

	rep(i, n + 1)rep(j, n + 1) dp[i][j] = inf;

	rep(i, n + 1) {
		dp[i][n] = n - i;
		dp[n][i] = n - i;
	}

	rrep(i, n) rrep(j, n) {
		if (a[i] == b[j]) {
			chmin(dp[i][j], dp[i + 1][j + 1] + 1);
		} else {
			//cerr << i << " " << j << endl;
			chmin(dp[i][j], dp[i + 1][j] + 1);
			chmin(dp[i][j], dp[i][j + 1] + 1);
		}
	}

	rep(i, n + 1)rep(j, n + 1)  if (dp[0][0] / 2 == dp[i][j]) num[i][j] = 1LL;

	rrep(i, n) rrep(j, n) {
		if (i + j > n) continue;
		//cerr << i << " " << j << endl;


		if (a[i] == b[j]) {
			if (dp[i][j] == dp[i + 1][j + 1] + 1) {
				num[i][j] += num[i + 1][j + 1];
			}
		} else {
			if (dp[i][j] == dp[i + 1][j] + 1) {
				num[i][j] += num[i + 1][j];
			}

			if (dp[i][j] == dp[i][j + 1] + 1) {
				num[i][j] += num[i][j + 1];
			}
		}
		chmin(num[i][j], inf);
	}

	/*
	rep(i, n + 1) {
		rep(j, n + 1) cout << dp[i][j] << " ";
		cout << endl;
	}
	

	
	rep(i, n + 1) {
		rep(j, n + 1) cout << num[i][j] << " ";
		cout << endl;
	}
	*/
	
	

	if (num[0][0] < k) {
		puts("NONE");
		return 0;
	}


	string ans = "";
	int ci = 0, cj = 0;

	while (1) {
		if (dp[ci][cj] == dp[0][0] / 2) break;

		if (a[ci] == b[cj]) {
			ans += a[ci];
			ci++, cj++;
			continue;
		}

		if (ci < n and (cj == n or dp[ci][cj] != dp[ci][cj + 1] + 1)) {
			ans += a[ci];
			ci++;
			continue;
		}

		if (cj < n and (ci == n or dp[ci][cj] != dp[ci + 1][cj] + 1)) {
			ans += b[cj];
			cj++;
			continue;
		}


		if (a[ci] < b[cj]) {
			if (k <= num[ci + 1][cj])
				ans += a[ci++];
			else
				k -= num[ci + 1][cj], ans += b[cj++];

		} else {
			//cerr << "Call " << ci << " " << cj  << " " << num[ci][cj + 1] << endl;
			if (k <= num[ci][cj + 1])
				ans += b[cj++];
			else
				k -= num[ci][cj + 1], ans += a[ci++];
		}
	}

	const int rest = dp[0][0] - int(ans.size());
	rrep(i,rest) ans += ans[i];
	cout << ans << endl;
	
	return 0;
}
```