/*  -*- coding: utf-8 -*-
 *
 * 1362.cc: Do Geese See God?
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 2000;
const long long LINF = 1LL << 61;

/* typedef */

typedef long long ll;

/* global variables */

char s[MAX_N + 4], t[MAX_N + 4];
int dp0[MAX_N][MAX_N + 1];
ll dp1[MAX_N][MAX_N + 1];

/* subroutines */

/* main */

int main() {
  ll k;
  scanf("%s%lld", s, &k);
  int n = strlen(s);
  k--;

  for (int i = 0; i < n; i++) {
    dp0[i][i + 1] = 1;
    dp1[i][i] = dp1[i][i + 1] = 1;
  }

  for (int l = 2; l <= n; l++)
    for (int i = 0, j = l; j <= n; i++, j++) {
      if (s[i] == s[j - 1]) {
	dp0[i][j] = dp0[i + 1][j - 1] + 2;
	dp1[i][j] = dp1[i + 1][j - 1];
      }
      else if (dp0[i][j - 1] == dp0[i + 1][j]) {
	dp0[i][j] = dp0[i][j - 1] + 2;
	dp1[i][j] = min(LINF, dp1[i][j - 1] + dp1[i + 1][j]);
      }
      else if (dp0[i][j - 1] < dp0[i + 1][j]) {
	dp0[i][j] = dp0[i][j - 1] + 2;
	dp1[i][j] = dp1[i][j - 1];
      }
      else {
	dp0[i][j] = dp0[i + 1][j] + 2;
	dp1[i][j] = dp1[i + 1][j];
      }
    }

  //printf("%d %lld\n", dp0[0][n], dp1[0][n]);

  int l = 0, mc = 0;
  for (int i = 0, j = n; i < j;) {
    if (s[i] == s[j - 1]) {
      if (i + 1 == j) {
	mc = s[i];
	break;
      }
      t[l++] = s[i];
      i++, j--;
    }
    else if (dp0[i][j - 1] == dp0[i + 1][j]) {
      char c0, c1;
      int i0, j0, i1, j1;
      if (s[i] < s[j - 1])
	c0 = s[i], c1 = s[j - 1], i0 = i + 1, j0 = j, i1 = i, j1 = j - 1;
      else
	c0 = s[j - 1], c1 = s[i], i0 = i, j0 = j - 1, i1 = i + 1, j1 = j;
      if (k < dp1[i0][j0])
	t[l++] = c0, i = i0, j = j0;
      else
	t[l++] = c1, i = i1, j = j1, k -= dp1[i0][j0];
    }
    else if (dp0[i][j - 1] < dp0[i + 1][j]) {
      t[l++] = s[j - 1];
      j--;
    }
    else {
      t[l++] = s[i];
      i++;
    }
  }

  if (k > 0) {
    puts("NONE");
    return 0;
  }

  for (int i = 0; i < l; i++) putchar(t[i]);
  if (mc) putchar(mc);
  for (int i = l - 1; i >= 0; i--) putchar(t[i]);
  putchar('\n');
  return 0;
}


### Prompt

Please formulate a cpp solution to the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
/*  -*- coding: utf-8 -*-
 *
 * 1362.cc: Do Geese See God?
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 2000;
const long long LINF = 1LL << 61;

/* typedef */

typedef long long ll;

/* global variables */

char s[MAX_N + 4], t[MAX_N + 4];
int dp0[MAX_N][MAX_N + 1];
ll dp1[MAX_N][MAX_N + 1];

/* subroutines */

/* main */

int main() {
  ll k;
  scanf("%s%lld", s, &k);
  int n = strlen(s);
  k--;

  for (int i = 0; i < n; i++) {
    dp0[i][i + 1] = 1;
    dp1[i][i] = dp1[i][i + 1] = 1;
  }

  for (int l = 2; l <= n; l++)
    for (int i = 0, j = l; j <= n; i++, j++) {
      if (s[i] == s[j - 1]) {
	dp0[i][j] = dp0[i + 1][j - 1] + 2;
	dp1[i][j] = dp1[i + 1][j - 1];
      }
      else if (dp0[i][j - 1] == dp0[i + 1][j]) {
	dp0[i][j] = dp0[i][j - 1] + 2;
	dp1[i][j] = min(LINF, dp1[i][j - 1] + dp1[i + 1][j]);
      }
      else if (dp0[i][j - 1] < dp0[i + 1][j]) {
	dp0[i][j] = dp0[i][j - 1] + 2;
	dp1[i][j] = dp1[i][j - 1];
      }
      else {
	dp0[i][j] = dp0[i + 1][j] + 2;
	dp1[i][j] = dp1[i + 1][j];
      }
    }

  //printf("%d %lld\n", dp0[0][n], dp1[0][n]);

  int l = 0, mc = 0;
  for (int i = 0, j = n; i < j;) {
    if (s[i] == s[j - 1]) {
      if (i + 1 == j) {
	mc = s[i];
	break;
      }
      t[l++] = s[i];
      i++, j--;
    }
    else if (dp0[i][j - 1] == dp0[i + 1][j]) {
      char c0, c1;
      int i0, j0, i1, j1;
      if (s[i] < s[j - 1])
	c0 = s[i], c1 = s[j - 1], i0 = i + 1, j0 = j, i1 = i, j1 = j - 1;
      else
	c0 = s[j - 1], c1 = s[i], i0 = i, j0 = j - 1, i1 = i + 1, j1 = j;
      if (k < dp1[i0][j0])
	t[l++] = c0, i = i0, j = j0;
      else
	t[l++] = c1, i = i1, j = j1, k -= dp1[i0][j0];
    }
    else if (dp0[i][j - 1] < dp0[i + 1][j]) {
      t[l++] = s[j - 1];
      j--;
    }
    else {
      t[l++] = s[i];
      i++;
    }
  }

  if (k > 0) {
    puts("NONE");
    return 0;
  }

  for (int i = 0; i < l; i++) putchar(t[i]);
  if (mc) putchar(mc);
  for (int i = l - 1; i >= 0; i--) putchar(t[i]);
  putchar('\n');
  return 0;
}


```