#include <cmath>
#include <vector>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <limits> 

using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<PII> VP;
typedef vector<ll> VL;
typedef vector<VL> VVL;
string s;
int n;
VVI pal_len;
VVL short_num;

void calc_len() {
	pal_len = VVI(n, VI(n, 1 << 25));
	for (int i = 0; i < n; ++i) {
		pal_len[i][i] = 1;
		if (i+1 < n) pal_len[i][i+1] = (s[i] == s[i+1]) ? 2 : 3;
	}
	for (int dist = 2; dist < n; ++dist) {
	  for (int i = 0, j = dist; j < n; ++i, j++) {
		if (s[i] == s[j]) pal_len[i][j] = 2 + pal_len[i+1][j-1];
		else pal_len[i][j] = 2 + min(pal_len[i+1][j], pal_len[i][j-1]);
	  }
	}
}
void calc_num() {
	short_num = VVL(n, VL(n, 0));
	for (int i = 0; i < n; ++i) {
		short_num[i][i] = 1;
		if (i+1 < n && s[i] == s[i+1]) short_num[i][i+1] = 1;
		if (i+1 < n && s[i] != s[i+1])  short_num[i][i+1] = 2;
	}
	for (int dist = 2; dist < n; ++dist) {
	  for (int i = 0, j = dist; j < n; ++i, j++) {
		if (s[i] == s[j]) short_num[i][j] = short_num[i+1][j-1];
		else if (pal_len[i+1][j] == pal_len[i][j-1]) {
			short_num[i][j] = short_num[i+1][j] + short_num[i][j-1];
			short_num[i][j] = min(short_num[i][j], 1LL << 61);
		} else 
			short_num[i][j] = (pal_len[i+1][j] < pal_len[i][j-1]) ?
					short_num[i+1][j] : short_num[i][j-1];
	  }
	}
}

void solve(int i, int j, ll k, string& sol) {
	if (i == j) { sol = s[i]; return; }
	if (i+1 == j && s[i] == s[j]) { sol = string(2, s[i]); return; }
	if (i+1 == j) {
		vector<string> pos;
		pos.push_back(string(1, s[i]) + string(1, s[j]) + string(1, s[i]));
		pos.push_back(string(1, s[j]) + string(1, s[i]) + string(1, s[j]));
		sort(pos.begin(), pos.end());
		if (k == 1) sol = pos[0];
		else sol = pos[1];
		return;
	}

	if (s[i] == s[j]) {
		solve(i+1, j-1, k, sol);
		if (sol.size() != 0) sol = s[i] + sol + s[j];
		return;
	} 
	if (pal_len[i+1][j] < pal_len[i][j-1] ||
		(pal_len[i+1][j] == pal_len[i][j-1] && s[i] < s[j] && k <= short_num[i+1][j])) {
		solve(i+1, j, k, sol);
		if (sol.size() != 0) sol = s[i] + sol + s[i];
		
		return;
	}
	if (pal_len[i+1][j] > pal_len[i][j-1] ||
		(pal_len[i+1][j] == pal_len[i][j-1] && s[i] > s[j] && k <= short_num[i][j-1])) {
		solve(i, j-1, k, sol);
		if (sol.size() != 0) sol = s[j] + sol + s[j];
		return;
	}
	if (s[i] < s[j]) {
		solve(i, j-1, k-short_num[i+1][j], sol);
		if (sol.size() != 0) sol = s[j] + sol + s[j];
		return;
	}
	solve(i+1, j, k-short_num[i][j-1], sol);
	if (sol.size() != 0) sol = s[i] + sol + s[i];
	return;
}

int main() {
	ios::sync_with_stdio(false);
	ll k;
	while (cin >> s) {
		cin >> k;
		n = s.size();
		calc_len();
		calc_num();
		if (short_num[0][n-1] < k) { cout << "NONE\n"; continue; }
		string sol = "";
		solve(0, n-1, k, sol);
		cout << sol << endl;
	}
}
### Prompt

Please create a solution in Cpp to the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <cmath>
#include <vector>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <limits> 

using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<PII> VP;
typedef vector<ll> VL;
typedef vector<VL> VVL;
string s;
int n;
VVI pal_len;
VVL short_num;

void calc_len() {
	pal_len = VVI(n, VI(n, 1 << 25));
	for (int i = 0; i < n; ++i) {
		pal_len[i][i] = 1;
		if (i+1 < n) pal_len[i][i+1] = (s[i] == s[i+1]) ? 2 : 3;
	}
	for (int dist = 2; dist < n; ++dist) {
	  for (int i = 0, j = dist; j < n; ++i, j++) {
		if (s[i] == s[j]) pal_len[i][j] = 2 + pal_len[i+1][j-1];
		else pal_len[i][j] = 2 + min(pal_len[i+1][j], pal_len[i][j-1]);
	  }
	}
}
void calc_num() {
	short_num = VVL(n, VL(n, 0));
	for (int i = 0; i < n; ++i) {
		short_num[i][i] = 1;
		if (i+1 < n && s[i] == s[i+1]) short_num[i][i+1] = 1;
		if (i+1 < n && s[i] != s[i+1])  short_num[i][i+1] = 2;
	}
	for (int dist = 2; dist < n; ++dist) {
	  for (int i = 0, j = dist; j < n; ++i, j++) {
		if (s[i] == s[j]) short_num[i][j] = short_num[i+1][j-1];
		else if (pal_len[i+1][j] == pal_len[i][j-1]) {
			short_num[i][j] = short_num[i+1][j] + short_num[i][j-1];
			short_num[i][j] = min(short_num[i][j], 1LL << 61);
		} else 
			short_num[i][j] = (pal_len[i+1][j] < pal_len[i][j-1]) ?
					short_num[i+1][j] : short_num[i][j-1];
	  }
	}
}

void solve(int i, int j, ll k, string& sol) {
	if (i == j) { sol = s[i]; return; }
	if (i+1 == j && s[i] == s[j]) { sol = string(2, s[i]); return; }
	if (i+1 == j) {
		vector<string> pos;
		pos.push_back(string(1, s[i]) + string(1, s[j]) + string(1, s[i]));
		pos.push_back(string(1, s[j]) + string(1, s[i]) + string(1, s[j]));
		sort(pos.begin(), pos.end());
		if (k == 1) sol = pos[0];
		else sol = pos[1];
		return;
	}

	if (s[i] == s[j]) {
		solve(i+1, j-1, k, sol);
		if (sol.size() != 0) sol = s[i] + sol + s[j];
		return;
	} 
	if (pal_len[i+1][j] < pal_len[i][j-1] ||
		(pal_len[i+1][j] == pal_len[i][j-1] && s[i] < s[j] && k <= short_num[i+1][j])) {
		solve(i+1, j, k, sol);
		if (sol.size() != 0) sol = s[i] + sol + s[i];
		
		return;
	}
	if (pal_len[i+1][j] > pal_len[i][j-1] ||
		(pal_len[i+1][j] == pal_len[i][j-1] && s[i] > s[j] && k <= short_num[i][j-1])) {
		solve(i, j-1, k, sol);
		if (sol.size() != 0) sol = s[j] + sol + s[j];
		return;
	}
	if (s[i] < s[j]) {
		solve(i, j-1, k-short_num[i+1][j], sol);
		if (sol.size() != 0) sol = s[j] + sol + s[j];
		return;
	}
	solve(i+1, j, k-short_num[i][j-1], sol);
	if (sol.size() != 0) sol = s[i] + sol + s[i];
	return;
}

int main() {
	ios::sync_with_stdio(false);
	ll k;
	while (cin >> s) {
		cin >> k;
		n = s.size();
		calc_len();
		calc_num();
		if (short_num[0][n-1] < k) { cout << "NONE\n"; continue; }
		string sol = "";
		solve(0, n-1, k, sol);
		cout << sol << endl;
	}
}
```