#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

int d[2020][2020];
ll g[2020][2020];
char A[2020];// "1trkvznlbqskroaokextbfscsfosftpbuvoxotdsvefnviqidzjmdegxlisrumfkpxlzuveovvthtqndm";//"1uzuzvzuw";
ll K;
int N, len;
char ans[4040];

void D(){for(int i=1;;i++);}

void Do(int L, int R, ll T, int id){
	//printf("%d %d %lld %lld %d\n", L, R, g[L][R], T, d[L-1][R+1]);
	if(L > R)return;
	if(L == R){
		ans[id] = A[L];
		//if(id != len/2+1)D();
		return;
	}
	
	if(A[L] == A[R]){
		ans[id] = ans[len + 1 - id] = A[L];
		Do(L+1, R-1, T, id+1);
	}
	else{
		if(A[L] < A[R]){
			if(d[L-1][R+1] + 2 == d[L][R+1]){
				if(g[L+1][R] >= T){
					ans[id] = ans[len + 1 - id] = A[L];
					Do(L+1, R, T, id+1);
				}
				else{
					ans[id] = ans[len + 1 - id] = A[R];
					Do(L, R-1, T - g[L+1][R], id+1);
				}
			}
			else{
				ans[id] = ans[len + 1 - id] = A[R];
				Do(L, R-1, T, id+1);
			}
		}
		else{
			if(d[L-1][R+1] + 2 == d[L-1][R]){
				if(g[L][R-1] >= T){
					ans[id] = ans[len + 1 - id] = A[R];
					Do(L, R-1, T, id+1);
				}
				else{
					ans[id] = ans[len + 1 - id] = A[L];
					Do(L+1, R, T - g[L][R-1], id+1);
				}
			}
			else{
				ans[id] = ans[len + 1 - id] = A[L];
				Do(L+1, R, T, id+1);
			}
		}
	}
}

void solve(int tc){
	scanf("%s", A+1);
	//srand(time(NULL));
	//for(int i=1;i<=2000;i++)A[i] = rand() % 26 + 'a';
	N = (int)strlen(A+1);
	
	d[0][N+1] = 0;
	for(int i=1;i<=N;i++)d[i][N+1] = 2*i, d[0][i] = 2*(N+1 - i);
	for(int i=1;i<=N;i++){
		for(int j=N;j>i;j--){
			d[i][j] = min(d[i-1][j] + 2, d[i][j+1] + 2);
			if(A[i] == A[j])d[i][j] = min(d[i][j], d[i-1][j+1] + 2);
		}
	}
	
	len = 2*N + 1;
	for(int i=1;i<=N;i++){
		len = min(len, 1 + d[i-1][i+1]);
	}
	for(int i=1;i<N;i++)len = min(len, d[i][i+1]);
	
	int chk = 0;
	for(int i=1;i<=N;i++){
		if(len == 1 + d[i-1][i+1]){
			g[i][i] = 1;
		}
	}
	for(int i=1;i<N;i++){
		if(len == d[i][i+1]){
			chk = g[i][i+1] = 1;
		}
	}
	
	for(int i=1+chk;i<N;i++){
		for(int j=1;j+i<=N;j++){
			if(A[j] == A[j+i] && d[j-1][j+i+1] + 2 == d[j][j+i])g[j][j+i] += g[j+1][j+i-1];
			if(A[j] != A[j+i]){
				if(d[j-1][j+i+1] + 2 == d[j-1][j+i])g[j][j+i] += g[j][j+i-1];
				if(d[j-1][j+i+1] + 2 == d[j][j+i+1])g[j][j+i] += g[j+1][j+i];
			}
			if(g[j][j+i] > 2e18)g[j][j+i] = 2e18;
		}
	}
	
//	for(int i=0;i<=N;i++){for(int j=1;j<=N+1;j++)printf("%-2d", d[i][j]);puts("");}
//	for(int i=1;i<=N;i++){for(int j=1;j<=N;j++)printf("%lld ", g[i][j]);puts("");}
	
	//printf("%lld\n", g[1][N]);
	//printf("%s\n", A+1);
	scanf("%lld", &K);
	if(g[1][N] < K)puts("NONE");
	else{
		Do(1, N, K, 1);
		printf("%s\n", ans+1);
	}
}

int main(){
	int Tc = 1;// scanf("%d",&Tc);
	for(int i=1;i<=Tc;i++){
		solve(i);
	}
	return 0;
}
### Prompt

Please formulate a CPP solution to the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

int d[2020][2020];
ll g[2020][2020];
char A[2020];// "1trkvznlbqskroaokextbfscsfosftpbuvoxotdsvefnviqidzjmdegxlisrumfkpxlzuveovvthtqndm";//"1uzuzvzuw";
ll K;
int N, len;
char ans[4040];

void D(){for(int i=1;;i++);}

void Do(int L, int R, ll T, int id){
	//printf("%d %d %lld %lld %d\n", L, R, g[L][R], T, d[L-1][R+1]);
	if(L > R)return;
	if(L == R){
		ans[id] = A[L];
		//if(id != len/2+1)D();
		return;
	}
	
	if(A[L] == A[R]){
		ans[id] = ans[len + 1 - id] = A[L];
		Do(L+1, R-1, T, id+1);
	}
	else{
		if(A[L] < A[R]){
			if(d[L-1][R+1] + 2 == d[L][R+1]){
				if(g[L+1][R] >= T){
					ans[id] = ans[len + 1 - id] = A[L];
					Do(L+1, R, T, id+1);
				}
				else{
					ans[id] = ans[len + 1 - id] = A[R];
					Do(L, R-1, T - g[L+1][R], id+1);
				}
			}
			else{
				ans[id] = ans[len + 1 - id] = A[R];
				Do(L, R-1, T, id+1);
			}
		}
		else{
			if(d[L-1][R+1] + 2 == d[L-1][R]){
				if(g[L][R-1] >= T){
					ans[id] = ans[len + 1 - id] = A[R];
					Do(L, R-1, T, id+1);
				}
				else{
					ans[id] = ans[len + 1 - id] = A[L];
					Do(L+1, R, T - g[L][R-1], id+1);
				}
			}
			else{
				ans[id] = ans[len + 1 - id] = A[L];
				Do(L+1, R, T, id+1);
			}
		}
	}
}

void solve(int tc){
	scanf("%s", A+1);
	//srand(time(NULL));
	//for(int i=1;i<=2000;i++)A[i] = rand() % 26 + 'a';
	N = (int)strlen(A+1);
	
	d[0][N+1] = 0;
	for(int i=1;i<=N;i++)d[i][N+1] = 2*i, d[0][i] = 2*(N+1 - i);
	for(int i=1;i<=N;i++){
		for(int j=N;j>i;j--){
			d[i][j] = min(d[i-1][j] + 2, d[i][j+1] + 2);
			if(A[i] == A[j])d[i][j] = min(d[i][j], d[i-1][j+1] + 2);
		}
	}
	
	len = 2*N + 1;
	for(int i=1;i<=N;i++){
		len = min(len, 1 + d[i-1][i+1]);
	}
	for(int i=1;i<N;i++)len = min(len, d[i][i+1]);
	
	int chk = 0;
	for(int i=1;i<=N;i++){
		if(len == 1 + d[i-1][i+1]){
			g[i][i] = 1;
		}
	}
	for(int i=1;i<N;i++){
		if(len == d[i][i+1]){
			chk = g[i][i+1] = 1;
		}
	}
	
	for(int i=1+chk;i<N;i++){
		for(int j=1;j+i<=N;j++){
			if(A[j] == A[j+i] && d[j-1][j+i+1] + 2 == d[j][j+i])g[j][j+i] += g[j+1][j+i-1];
			if(A[j] != A[j+i]){
				if(d[j-1][j+i+1] + 2 == d[j-1][j+i])g[j][j+i] += g[j][j+i-1];
				if(d[j-1][j+i+1] + 2 == d[j][j+i+1])g[j][j+i] += g[j+1][j+i];
			}
			if(g[j][j+i] > 2e18)g[j][j+i] = 2e18;
		}
	}
	
//	for(int i=0;i<=N;i++){for(int j=1;j<=N+1;j++)printf("%-2d", d[i][j]);puts("");}
//	for(int i=1;i<=N;i++){for(int j=1;j<=N;j++)printf("%lld ", g[i][j]);puts("");}
	
	//printf("%lld\n", g[1][N]);
	//printf("%s\n", A+1);
	scanf("%lld", &K);
	if(g[1][N] < K)puts("NONE");
	else{
		Do(1, N, K, 1);
		printf("%s\n", ans+1);
	}
}

int main(){
	int Tc = 1;// scanf("%d",&Tc);
	for(int i=1;i<=Tc;i++){
		solve(i);
	}
	return 0;
}
```