#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll, ll> pii;
const int MOD = 1000000007;
const ll INF = 1e18 + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
string s; ll k;
vector<vector<pii>> dp;

pii solve(int l, int r)
{
	if (dp[l][r].first >= 0) return dp[l][r];
	pii res(INF, INF);
	if (l == r) return pii(1, 1);
	else if (r - l == 1)
	{
		if (s[l] == s[r]) res = pii(2, 1);
		else res = pii(3, 2);
	}
	else
	{
		if (s[l] == s[r]) res = pii(solve(l + 1, r - 1).first + 2, solve(l + 1, r - 1).second);
		else
		{
			pii tmp1 = solve(l + 1, r), tmp2 = solve(l, r - 1);
			if (tmp1.first == tmp2.first) res = pii(tmp1.first + 2, tmp1.second + tmp2.second);
			else res = pii(min(tmp1, tmp2).first + 2, min(tmp1, tmp2).second);
		}
	}
	return dp[l][r] = pii(res.first, min(res.second, INF));
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	cin >> s >> k;
	dp.resize(2222, vector<pii>(2222, pii(-1, -1)));
	int n = s.size();
	ll len = solve(0, n - 1).first, c = solve(0, n - 1).second;
	if (c < k)
	{
		cout << "NONE" << endl;
		return 0;
	}
	k--;
	string ans(len, '#');
	int ansl = 0, ansr = len - 1, tmp = 0, l = 0, r = n - 1;
	while(1)
	{
		if (l == r)
		{
			ans[ansl] = s[l];
			break;
		}
		if (l > r) break;
		if (s[l] == s[r])
		{
			ans[ansl] = ans[ansr] = s[l];
			ansl++; ansr--;
			l++; r--;
		}
		else
		{
			bool f;
			if (solve(l + 1, r).first < solve(l, r - 1).first) f = true;
			else if (solve(l, r - 1).first < solve(l + 1, r).first) f = false;
			else
			{
				if (s[l] < s[r])
				{
					if (solve(l + 1, r).second <= k)
					{
						k -= solve(l + 1, r).second;
						f = false;
					}
					else f = true;
				}
				else if(s[l] > s[r])
				{
					if (solve(l, r - 1).second <= k)
					{
						k -= solve(l, r - 1).second;
						f = true;
					}
					else f = false;
				}
			}
			if (f)
			{
				ans[ansl] = ans[ansr] = s[l];
				ansl++; ansr--;
				l++;
			}
			else
			{
				ans[ansl] = ans[ansr] = s[r];
				ansl++; ansr--;
				r--;
			}
		}
	}
	cout << ans << endl;
	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;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll, ll> pii;
const int MOD = 1000000007;
const ll INF = 1e18 + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
string s; ll k;
vector<vector<pii>> dp;

pii solve(int l, int r)
{
	if (dp[l][r].first >= 0) return dp[l][r];
	pii res(INF, INF);
	if (l == r) return pii(1, 1);
	else if (r - l == 1)
	{
		if (s[l] == s[r]) res = pii(2, 1);
		else res = pii(3, 2);
	}
	else
	{
		if (s[l] == s[r]) res = pii(solve(l + 1, r - 1).first + 2, solve(l + 1, r - 1).second);
		else
		{
			pii tmp1 = solve(l + 1, r), tmp2 = solve(l, r - 1);
			if (tmp1.first == tmp2.first) res = pii(tmp1.first + 2, tmp1.second + tmp2.second);
			else res = pii(min(tmp1, tmp2).first + 2, min(tmp1, tmp2).second);
		}
	}
	return dp[l][r] = pii(res.first, min(res.second, INF));
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	cin >> s >> k;
	dp.resize(2222, vector<pii>(2222, pii(-1, -1)));
	int n = s.size();
	ll len = solve(0, n - 1).first, c = solve(0, n - 1).second;
	if (c < k)
	{
		cout << "NONE" << endl;
		return 0;
	}
	k--;
	string ans(len, '#');
	int ansl = 0, ansr = len - 1, tmp = 0, l = 0, r = n - 1;
	while(1)
	{
		if (l == r)
		{
			ans[ansl] = s[l];
			break;
		}
		if (l > r) break;
		if (s[l] == s[r])
		{
			ans[ansl] = ans[ansr] = s[l];
			ansl++; ansr--;
			l++; r--;
		}
		else
		{
			bool f;
			if (solve(l + 1, r).first < solve(l, r - 1).first) f = true;
			else if (solve(l, r - 1).first < solve(l + 1, r).first) f = false;
			else
			{
				if (s[l] < s[r])
				{
					if (solve(l + 1, r).second <= k)
					{
						k -= solve(l + 1, r).second;
						f = false;
					}
					else f = true;
				}
				else if(s[l] > s[r])
				{
					if (solve(l, r - 1).second <= k)
					{
						k -= solve(l, r - 1).second;
						f = true;
					}
					else f = false;
				}
			}
			if (f)
			{
				ans[ansl] = ans[ansr] = s[l];
				ansl++; ansr--;
				l++;
			}
			else
			{
				ans[ansl] = ans[ansr] = s[r];
				ansl++; ansr--;
				r--;
			}
		}
	}
	cout << ans << endl;
	return 0;
}
```