Example

Input

crc
1


Output

crc
#include <iostream>
#include <string>

using namespace std;

const long long INF = 1LL << 60;

static int len[2000][2000];
static long long pattern[2000][2000];

int main(){
	string S;
	while(cin >> S){
		long long K; cin >> K;
		int n = S.size();
		for(int i=0;i<n;i++){
			len[i][i] = 1;
			pattern[i][i] = 1;
		}
		for(int i=0;i+1<n;i++){
			len[i][i+1] = (S[i] == S[i+1] ? 2 : 3);
			pattern[i][i+1] = (S[i] == S[i+1] ? 1 : 2);
		}
		for(int d=2;d<n;d++){
			for(int i=0;i+d<n;i++){
				if(S[i] == S[i+d]){
					len[i][i+d] = len[i+1][i+d-1] + 2;
					pattern[i][i+d] = pattern[i+1][i+d-1];
				} else {
					len[i][i+d] = min(len[i+1][i+d], len[i][i+d-1]) + 2;
					pattern[i][i+d] = 0;
					if(len[i+1][i+d] <= len[i][i+d-1]){
						pattern[i][i+d] = min(INF, pattern[i][i+d] + pattern[i+1][i+d]);
					}
					if(len[i+1][i+d] >= len[i][i+d-1]){
						pattern[i][i+d] = min(INF, pattern[i][i+d] + pattern[i][i+d-1]);
					}
				}
			}
		}
		--K;
		if(pattern[0][n-1] <= K){
			cout << "NONE" << endl;
			continue;
		}
		string res = string(len[0][n-1], '.');
		int rs = 0, re = res.size() - 1;
		int idxA = 0, idxB = n-1;
		while(idxA < idxB){
			if(S[idxA] == S[idxB]){
				res[rs] = res[re] = S[idxA];
				++rs;
				--re;
				++idxA;
				--idxB;
			} else {
				bool useFront = true;
				if(len[idxA+1][idxB] < len[idxA][idxB-1]){
				} else if(len[idxA][idxB-1] < len[idxA+1][idxB]){
					useFront = false;
				} else {
					if(S[idxA] < S[idxB]){
						if(pattern[idxA+1][idxB] <= K){
							K -= pattern[idxA+1][idxB];
							useFront = false;
						}
					} else {
						if(pattern[idxA][idxB-1] <= K){
							K -= pattern[idxA][idxB-1];
						} else {
							useFront = false;
						}
					}
				}
				if(useFront){
					res[rs] = res[re] = S[idxA];
					++rs;
					--re;
					++idxA;
				} else {
					res[rs] = res[re] = S[idxB];
					++rs;
					--re;
					--idxB;
				}
			}
		}
		if(idxA == idxB) res[rs] = S[idxA];
		cout << res << endl;
	}
}