Example

Input

crc
1


Output

crc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

string S;
ll K;
P memo[4010][4010];

P dfs(int l, int r){
	if(memo[l][r].first != -1) return memo[l][r];
	
	P ret;
	if(l == r) ret = {1, 1};
	else if(l == r - 1){
		if(S[l] == S[r]) ret = {2, 1};
		else ret = {3, 2};
	}else{
		if(S[l] == S[r]){
			P p = dfs(l + 1, r - 1);
			p.first += 2;
			ret = p;
		}else{
			P p1 = dfs(l + 1, r);
			P p2 = dfs(l, r - 1);
			if(p1.first == p2.first){
				p1.second += p2.second;
				p1.first += 2;
				if(p1.second > K) p1.second = K + 1;
				ret = p1;
			}else if(p1.first < p2.first){
				p1.first += 2;
				ret = p1;
			}else{
				p2.first += 2;
				ret = p2;
			}
		}
	}
	return memo[l][r] = ret;
}
string dfs2(int l, int r, ll k){
	//cout << l << " " << r << " " << k << endl;
	if(l == r){
		assert(k == 1);
		return S.substr(l, 1);
	}else if(l == r - 1){
		if(S[l] == S[r]){
			assert(k == 1);
			return S.substr(l, 2);
		}else{
			assert(k <= 2);
			string ret;
			ret.resize(3);
			char cl = S[l];
			char cr = S[r];
			if(k == 1){
				ret[0] = min(cl, cr);
				ret[1] = max(cl, cr);
				ret[2] = min(cl, cr);
			}else{
				ret[0] = max(cl, cr);
				ret[1] = min(cl, cr);
				ret[2] = max(cl, cr);
			}
			return ret;
		}
	}else{
		if(S[l] == S[r]){
			return  S[l] + dfs2(l + 1, r - 1, k) + S[r];
		}else{
			P p1 = dfs(l + 1, r);
			P p2 = dfs(l, r - 1);
			if(p1.first == p2.first){
				if(S[l] < S[r]){
					if(p1.second >= k){
						return  S[l] + dfs2(l + 1, r, k) + S[l];
					}else{
						return  S[r] + dfs2(l, r - 1, k - p1.second) + S[r];
					}
				}else{
					if(p2.second >= k){
						return  S[r] + dfs2(l, r - 1, k) + S[r];
					}else{
						return  S[l] + dfs2(l + 1, r, k - p2.second) + S[l];
					}
				}
			}else if(p1.first < p2.first){
				return  S[l] + dfs2(l + 1, r, k) + S[l];
			}else{
				return  S[r] + dfs2(l, r - 1, k) + S[r];
			}
		}
	}
}


int main(){
	cin >> S;
	cin >> K;
	for(int i = 0; i < 4010; i++){
		for(int j = 0; j < 4010; j++){
			memo[i][j].first = -1;
		}
	}
	P ret = dfs(0, S.size() - 1);
	if(ret.second < K){
		cout << "NONE" << endl;
	}else{
		cout << dfs2(0, S.size() - 1, K) << endl;
	}
}