#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;
struct node{int l;ll s;} f[2010][2010];
char ans[4010],a[2010];
int n,t;
ll k;

void print()
{
  for (int i=t;i;i--)
    printf("%c",ans[i]);
  cout <<endl;
}
void work(int l,int r,ll k)
{
  if (l==r) {printf("%s%c",ans+1,a[l]); print();return ;}
  if (l==r-1&&a[l]==a[r]) {ans[++t]=a[l]; printf("%s",ans+1); print(); return;}
  if (a[l]==a[r]) {ans[++t]=a[l]; work(l+1,r-1,k);}
  else {
      if (f[l+1][r].l>f[l][r-1].l) {ans[++t]=a[r];work(l,r-1,k);}
      else if (f[l+1][r].l<f[l][r-1].l) {ans[++t]=a[l];work(l+1,r,k);}
      else {
          if (a[l]>a[r])
          {
            if (f[l][r-1].s>=k) {ans[++t]=a[r];work(l,r-1,k);}
            else {ans[++t]=a[l];work(l+1,r,k-f[l][r-1].s);}
          }
          else {
            if (f[l+1][r].s>=k) {ans[++t]=a[l];work(l+1,r,k);}
            else {ans[++t]=a[r];work(l,r-1,k-f[l+1][r].s);}
          }
      }
  }
}

int main()
{
  //freopen("1.in","r",stdin);
  scanf("%s",a+1);
  cin>>k;
  n=strlen(a+1);
  for (int i=1; i<=n; i++) f[i][i]=(node){0,1};
  for (int i=1;i<=n-1;i++)
    if (a[i]==a[i+1]) f[i][i+1]=(node){0,1};
    else f[i][i+1]=(node){1,2};
  for (int l=3; l<=n; l++)
    for (int i=1; i<=n-l+1;i++)
    {
      int j=i+l-1;
      if (a[i]==a[j]) f[i][j]=f[i+1][j-1];
      else {
        if (f[i+1][j].l>f[i][j-1].l) f[i][j]=(node){f[i][j-1].l+1,f[i][j-1].s};
        else if (f[i+1][j].l<f[i][j-1].l) f[i][j]=(node){f[i+1][j].l+1,f[i+1][j].s};
        else f[i][j]=(node){f[i][j-1].l+1,f[i+1][j].s+f[i][j-1].s};
      }
      if (f[i][j].s>k) f[i][j].s=k+1;
    }
  if (f[1][n].s<k) puts("NONE");
    else work(1,n,k);
  return 0;
}
### Prompt

Generate a CPP solution to the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;
struct node{int l;ll s;} f[2010][2010];
char ans[4010],a[2010];
int n,t;
ll k;

void print()
{
  for (int i=t;i;i--)
    printf("%c",ans[i]);
  cout <<endl;
}
void work(int l,int r,ll k)
{
  if (l==r) {printf("%s%c",ans+1,a[l]); print();return ;}
  if (l==r-1&&a[l]==a[r]) {ans[++t]=a[l]; printf("%s",ans+1); print(); return;}
  if (a[l]==a[r]) {ans[++t]=a[l]; work(l+1,r-1,k);}
  else {
      if (f[l+1][r].l>f[l][r-1].l) {ans[++t]=a[r];work(l,r-1,k);}
      else if (f[l+1][r].l<f[l][r-1].l) {ans[++t]=a[l];work(l+1,r,k);}
      else {
          if (a[l]>a[r])
          {
            if (f[l][r-1].s>=k) {ans[++t]=a[r];work(l,r-1,k);}
            else {ans[++t]=a[l];work(l+1,r,k-f[l][r-1].s);}
          }
          else {
            if (f[l+1][r].s>=k) {ans[++t]=a[l];work(l+1,r,k);}
            else {ans[++t]=a[r];work(l,r-1,k-f[l+1][r].s);}
          }
      }
  }
}

int main()
{
  //freopen("1.in","r",stdin);
  scanf("%s",a+1);
  cin>>k;
  n=strlen(a+1);
  for (int i=1; i<=n; i++) f[i][i]=(node){0,1};
  for (int i=1;i<=n-1;i++)
    if (a[i]==a[i+1]) f[i][i+1]=(node){0,1};
    else f[i][i+1]=(node){1,2};
  for (int l=3; l<=n; l++)
    for (int i=1; i<=n-l+1;i++)
    {
      int j=i+l-1;
      if (a[i]==a[j]) f[i][j]=f[i+1][j-1];
      else {
        if (f[i+1][j].l>f[i][j-1].l) f[i][j]=(node){f[i][j-1].l+1,f[i][j-1].s};
        else if (f[i+1][j].l<f[i][j-1].l) f[i][j]=(node){f[i+1][j].l+1,f[i+1][j].s};
        else f[i][j]=(node){f[i][j-1].l+1,f[i+1][j].s+f[i][j-1].s};
      }
      if (f[i][j].s>k) f[i][j].s=k+1;
    }
  if (f[1][n].s<k) puts("NONE");
    else work(1,n,k);
  return 0;
}
```