#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define L 2003

string s;
int n;
ll k;
int cost[L][L];
ll dp[L][L];
vector<P> ps;
string ans;

void solve() {
  rep(i, n+1) rep(j, n+1) cost[i][j] = INF;
  cost[0][n] = 0;
  priority_queue<IP, vector<IP>, greater<IP> > que;
  que.push(IP(0, P(0, n)));
  while(!que.empty()) {
    IP ip = que.top();
    int d = ip.first, a = ip.second.first, b = ip.second.second;
    que.pop();
    if(cost[a][b] < d) continue;
    ps.emplace_back(P(a, b));
    if(a+1 == b) {
      if(d+1 < cost[a+1][b]) {
        cost[a+1][b] = d+1;
      }
    } else if(s[a] == s[b-1]) {
      if(d+2 < cost[a+1][b-1]) {
        cost[a+1][b-1] = d+2;
        if(a+1 < b-1) que.push(IP(d+2, P(a+1, b-1)));
      }
    } else {
      if(d+2 < cost[a+1][b]) {
        cost[a+1][b] = d+2;
        if(a+1 < b) que.push(IP(d+2, P(a+1, b)));
      }
      if(d+2 < cost[a][b-1]) {
        cost[a][b-1] = d+2;
        if(a < b-1) que.push(IP(d+2, P(a, b-1)));
      }
    }
  }
  int ln = INF;
  rep(i, n+1) ln = min(ln, cost[i][i]);
  rep(i, n+1) {
    if(ln == cost[i][i]) {
      dp[i][i] = 1;
    }
  }

  for(auto it = ps.rbegin(); it != ps.rend(); ++it) {
    P &p = (*it);
    int a = p.first, b = p.second;
    int d = cost[a][b];
    ll r = 0;
    if(a+1 == b) {
      if(d+1 == cost[a+1][b]) r = dp[a+1][b];
    } else if(s[a] == s[b-1]) {
      if(d+2 == cost[a+1][b-1]) r = dp[a+1][b-1];
    } else {
      if(d+2 == cost[a+1][b]) r += dp[a+1][b];
      if(d+2 == cost[a][b-1]) r += dp[a][b-1];
    }
    if(r > INFLL) r = INFLL;
    dp[a][b] = r;
  }
  if(dp[0][n] < k) {
    cout << "NONE" << endl;
    return;
  }

  ans.resize(ln);
  int a = 0, b = n, left = 0, right = ln;
  while(a < b) {
    if(a+1 == b) {
      ans[left++] = s[a];
      ++a;
    } else if(s[a] == s[b-1]) {
      ans[left++] = s[a];
      ans[--right] = s[b-1];
      ++a; --b;
    } else if(s[a] < s[b-1]) {
      bool c = (cost[a][b]+2 == cost[a+1][b]);
      if(c && k <= dp[a+1][b]) {
        ans[left++] = s[a];
        ans[--right] = s[a];
        ++a;
      } else {
        if(c) k -= dp[a+1][b];
        ans[left++] = s[b-1];
        ans[--right] = s[b-1];
        --b;
      }
    } else {
      bool c = (cost[a][b]+2 == cost[a][b-1]);
      if(c && k <= dp[a][b-1]) {
        ans[left++] = s[b-1];
        ans[--right] = s[b-1];
        --b;
      } else {
        if(c) k -= dp[a][b-1];
        ans[left++] = s[a];
        ans[--right] = s[a];
        ++a;
      }
    }
  }
  cout << ans << endl;
}

int main() {
  cin >> s >> k;
  n = s.length();
  solve();
  return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define L 2003

string s;
int n;
ll k;
int cost[L][L];
ll dp[L][L];
vector<P> ps;
string ans;

void solve() {
  rep(i, n+1) rep(j, n+1) cost[i][j] = INF;
  cost[0][n] = 0;
  priority_queue<IP, vector<IP>, greater<IP> > que;
  que.push(IP(0, P(0, n)));
  while(!que.empty()) {
    IP ip = que.top();
    int d = ip.first, a = ip.second.first, b = ip.second.second;
    que.pop();
    if(cost[a][b] < d) continue;
    ps.emplace_back(P(a, b));
    if(a+1 == b) {
      if(d+1 < cost[a+1][b]) {
        cost[a+1][b] = d+1;
      }
    } else if(s[a] == s[b-1]) {
      if(d+2 < cost[a+1][b-1]) {
        cost[a+1][b-1] = d+2;
        if(a+1 < b-1) que.push(IP(d+2, P(a+1, b-1)));
      }
    } else {
      if(d+2 < cost[a+1][b]) {
        cost[a+1][b] = d+2;
        if(a+1 < b) que.push(IP(d+2, P(a+1, b)));
      }
      if(d+2 < cost[a][b-1]) {
        cost[a][b-1] = d+2;
        if(a < b-1) que.push(IP(d+2, P(a, b-1)));
      }
    }
  }
  int ln = INF;
  rep(i, n+1) ln = min(ln, cost[i][i]);
  rep(i, n+1) {
    if(ln == cost[i][i]) {
      dp[i][i] = 1;
    }
  }

  for(auto it = ps.rbegin(); it != ps.rend(); ++it) {
    P &p = (*it);
    int a = p.first, b = p.second;
    int d = cost[a][b];
    ll r = 0;
    if(a+1 == b) {
      if(d+1 == cost[a+1][b]) r = dp[a+1][b];
    } else if(s[a] == s[b-1]) {
      if(d+2 == cost[a+1][b-1]) r = dp[a+1][b-1];
    } else {
      if(d+2 == cost[a+1][b]) r += dp[a+1][b];
      if(d+2 == cost[a][b-1]) r += dp[a][b-1];
    }
    if(r > INFLL) r = INFLL;
    dp[a][b] = r;
  }
  if(dp[0][n] < k) {
    cout << "NONE" << endl;
    return;
  }

  ans.resize(ln);
  int a = 0, b = n, left = 0, right = ln;
  while(a < b) {
    if(a+1 == b) {
      ans[left++] = s[a];
      ++a;
    } else if(s[a] == s[b-1]) {
      ans[left++] = s[a];
      ans[--right] = s[b-1];
      ++a; --b;
    } else if(s[a] < s[b-1]) {
      bool c = (cost[a][b]+2 == cost[a+1][b]);
      if(c && k <= dp[a+1][b]) {
        ans[left++] = s[a];
        ans[--right] = s[a];
        ++a;
      } else {
        if(c) k -= dp[a+1][b];
        ans[left++] = s[b-1];
        ans[--right] = s[b-1];
        --b;
      }
    } else {
      bool c = (cost[a][b]+2 == cost[a][b-1]);
      if(c && k <= dp[a][b-1]) {
        ans[left++] = s[b-1];
        ans[--right] = s[b-1];
        --b;
      } else {
        if(c) k -= dp[a][b-1];
        ans[left++] = s[a];
        ans[--right] = s[a];
        ++a;
      }
    }
  }
  cout << ans << endl;
}

int main() {
  cin >> s >> k;
  n = s.length();
  solve();
  return 0;
}

```