Example

Input

crc
1


Output

crc
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int64 INF = 1LL << 60;                        
string S;
int64 k, dp[2000][2000], dp2[2000][2000];

inline void merge(int64& a, int64 b)
{
  a = min(a + b, INF);
}

int main()
{
  cin >> S;
  cin >> k; --k;

  for(int i = 0; i < S.size(); i++) {
    dp[i][i] = 1, dp2[i][i] = 1;
  }
  for(int i = 0; i < S.size() - 1; i++) {
    if(S[i] == S[i + 1]) dp[i][i + 1] = 2, dp2[i][i + 1] = 1;
    else                 dp[i][i + 1] = 3, dp2[i][i + 1] = 2;
  }
  for(int k = 2; k < S.size(); k++) {
    for(int i = k; i < S.size(); i++) {
      if(S[i - k] == S[i]) {
        dp[i - k][i] = dp[i - k + 1][i - 1] + 2;
        merge(dp2[i - k][i], dp2[i - k + 1][i - 1]);
      } else {
        dp[i - k][i] = min(dp[i - k + 1][i], dp[i - k][i - 1]) + 2;
        if(dp[i - k + 1][i] + 2 == dp[i - k][i]) merge(dp2[i - k][i], dp2[i - k + 1][i]);
        if(dp[i - k][i - 1] + 2 == dp[i - k][i]) merge(dp2[i - k][i], dp2[i - k][i - 1]);
      }
    }
  }

  if(dp2[0][S.size() - 1] <= k) {
    cout << "NONE" << endl;
  } else {
    int l = 0, r = S.size() - 1;
    string L, R;
    while(l < r) {
      if(S[l] == S[r]) {
        L += S[l++], R += S[r--];
      } else {
        bool which;
        if(dp[l + 1][r] < dp[l][r - 1]) {
          which = false;
        } else if(dp[l + 1][r] > dp[l][r - 1]) {
          which = true;
        } else if(S[l] < S[r]) {
          if(dp2[l + 1][r] <= k) k -= dp2[l + 1][r], which = true;
          else which = false;
        } else {
          if(dp2[l][r - 1] <= k) k -= dp2[l][r - 1], which = false;
          else which = true;
        }
        if(!which) {
          L += S[l], R += S[l++];
        } else {
          L += S[r], R += S[r--];
        }
      }
    }
    if(l == r) L += S[l];
    reverse(R.begin(), R.end());
    cout << L << R << endl;
  }
}