#include<bits/stdc++.h>
using namespace std;
#define int long long
using Int = __int128;
int dp[2222][2222];
bool used[2222][2222];
bool used2[2222][2222];
Int dp2[2222][2222];
struct st{
  int l,r,c;
  st(){}
  st(int l,int r,int c):l(l),r(r),c(c){}
  bool operator<(const st &a)const{
    return c>a.c;
  }
};
string s;
int k,n;
Int K;
Int dfs(int l,int r){
  if(used2[l][r]) return dp2[l][r];
  used2[l][r]=1;
  //cout<<l<<" "<<r<<endl;
  if(r-l<2){
    return dp2[l][r]=1;
  }
  map<char,Int> m;
  if(used[l+1][r-1]&&s[l]==s[r-1]&&dp[l][r]==dp[l+1][r-1]+2){
    if(m.count(s[l])) assert(m[s[l]]==dfs(l+1,r-1));
    m[s[l]]=dfs(l+1,r-1);
  }else{
    if(used[l+1][r]&&dp[l][r]==dp[l+1][r]+2){
      //cout<<l<<" "<<r<<":"<<(int)m[s[l]]<<" "<<(int)dfs(l+1,r)<<endl;
      if(m.count(s[l])) assert(m[s[l]]==dfs(l+1,r));
      m[s[l]]=dfs(l+1,r);
    }
    if(used[l][r-1]&&dp[l][r]==dp[l][r-1]+2){
      if(m.count(s[r-1])) assert(m[s[r-1]]==dfs(l,r-1));
      m[s[r-1]]=dfs(l,r-1);
    }
  }
  Int res=0;
  for(auto p:m){
    res+=p.second;
    if(res>LLONG_MAX) res=LLONG_MAX;
  }
  //cout<<l<<" "<<r<<":"<<(int)res<<endl;
  return dp2[l][r]=res;
}
string ans;
void dfs2(int l,int r,Int x){
  //cout<<l<<" "<<r<<":"<<(int)x<<endl;
  if(r-l<2){
    cout<<ans;
    if(l<r) cout<<s[l];
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    return;
  }
  map<char,Int> m;
  typedef pair<int,int> P;
  map<char,P> mp;
  if(s[l]==s[r-1]&&dp[l][r]==dp[l+1][r-1]+2){
    //if(m.count(s[l])) assert(m[s[l]]==dfs(l+1,r-1));
    m[s[l]]=dfs(l+1,r-1);
    mp[s[l]]=P(+1,-1);
  }else{
    if(dp[l][r]==dp[l+1][r]+2){
      //if(m.count(s[l])) assert(m[s[l]]==dfs(l+1,r));
      m[s[l]]=dfs(l+1,r);
      mp[s[l]]=P(+1,0);
    }
    if(dp[l][r]==dp[l][r-1]+2){
      //if(m.count(s[r-1])) assert(m[s[r-1]]==dfs(l,r-1));
      m[s[r-1]]=dfs(l,r-1);
      mp[s[r-1]]=P(0,-1);
    }
  }
  for(auto p:m){
    if(p.second<x){
      x-=p.second;
      continue;
    }
    ans+=p.first;
    dfs2(l+mp[p.first].first,r+mp[p.first].second,x);
    break;
  }
}
signed main(){
  cin>>s>>k;
  K=k;
  n=s.size();
  memset(used,0,sizeof(used));
  priority_queue<st> q;
  for(int i=0;i<n;i++){
    q.push(st(i,i,0));
    q.push(st(i,i+1,1));
  }
  while(!q.empty()){
    st p=q.top();q.pop();
    int l=p.l,r=p.r,c=p.c;
    if(used[l][r]) continue;
    used[l][r]=1;
    dp[l][r]=c;
    if(l>0&&r<n) if(s[l-1]==s[r]) q.push(st(l-1,r+1,c+2));
    if(l>0) q.push(st(l-1,r,c+2));
    if(r<n) q.push(st(l,r+1,c+2));
  }
  //cout<<dp[0][n]<<endl;
  memset(used2,0,sizeof(used2));
  dfs(0,n);
  //cout<<(int)dp2[0][n]<<endl;
  if(dp2[0][n]<K){
    cout<<"NONE"<<endl;
    return 0;
  }
  dfs2(0,n,K);
  return 0;
}
### Prompt

Create a solution in CPP for the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
using Int = __int128;
int dp[2222][2222];
bool used[2222][2222];
bool used2[2222][2222];
Int dp2[2222][2222];
struct st{
  int l,r,c;
  st(){}
  st(int l,int r,int c):l(l),r(r),c(c){}
  bool operator<(const st &a)const{
    return c>a.c;
  }
};
string s;
int k,n;
Int K;
Int dfs(int l,int r){
  if(used2[l][r]) return dp2[l][r];
  used2[l][r]=1;
  //cout<<l<<" "<<r<<endl;
  if(r-l<2){
    return dp2[l][r]=1;
  }
  map<char,Int> m;
  if(used[l+1][r-1]&&s[l]==s[r-1]&&dp[l][r]==dp[l+1][r-1]+2){
    if(m.count(s[l])) assert(m[s[l]]==dfs(l+1,r-1));
    m[s[l]]=dfs(l+1,r-1);
  }else{
    if(used[l+1][r]&&dp[l][r]==dp[l+1][r]+2){
      //cout<<l<<" "<<r<<":"<<(int)m[s[l]]<<" "<<(int)dfs(l+1,r)<<endl;
      if(m.count(s[l])) assert(m[s[l]]==dfs(l+1,r));
      m[s[l]]=dfs(l+1,r);
    }
    if(used[l][r-1]&&dp[l][r]==dp[l][r-1]+2){
      if(m.count(s[r-1])) assert(m[s[r-1]]==dfs(l,r-1));
      m[s[r-1]]=dfs(l,r-1);
    }
  }
  Int res=0;
  for(auto p:m){
    res+=p.second;
    if(res>LLONG_MAX) res=LLONG_MAX;
  }
  //cout<<l<<" "<<r<<":"<<(int)res<<endl;
  return dp2[l][r]=res;
}
string ans;
void dfs2(int l,int r,Int x){
  //cout<<l<<" "<<r<<":"<<(int)x<<endl;
  if(r-l<2){
    cout<<ans;
    if(l<r) cout<<s[l];
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    return;
  }
  map<char,Int> m;
  typedef pair<int,int> P;
  map<char,P> mp;
  if(s[l]==s[r-1]&&dp[l][r]==dp[l+1][r-1]+2){
    //if(m.count(s[l])) assert(m[s[l]]==dfs(l+1,r-1));
    m[s[l]]=dfs(l+1,r-1);
    mp[s[l]]=P(+1,-1);
  }else{
    if(dp[l][r]==dp[l+1][r]+2){
      //if(m.count(s[l])) assert(m[s[l]]==dfs(l+1,r));
      m[s[l]]=dfs(l+1,r);
      mp[s[l]]=P(+1,0);
    }
    if(dp[l][r]==dp[l][r-1]+2){
      //if(m.count(s[r-1])) assert(m[s[r-1]]==dfs(l,r-1));
      m[s[r-1]]=dfs(l,r-1);
      mp[s[r-1]]=P(0,-1);
    }
  }
  for(auto p:m){
    if(p.second<x){
      x-=p.second;
      continue;
    }
    ans+=p.first;
    dfs2(l+mp[p.first].first,r+mp[p.first].second,x);
    break;
  }
}
signed main(){
  cin>>s>>k;
  K=k;
  n=s.size();
  memset(used,0,sizeof(used));
  priority_queue<st> q;
  for(int i=0;i<n;i++){
    q.push(st(i,i,0));
    q.push(st(i,i+1,1));
  }
  while(!q.empty()){
    st p=q.top();q.pop();
    int l=p.l,r=p.r,c=p.c;
    if(used[l][r]) continue;
    used[l][r]=1;
    dp[l][r]=c;
    if(l>0&&r<n) if(s[l-1]==s[r]) q.push(st(l-1,r+1,c+2));
    if(l>0) q.push(st(l-1,r,c+2));
    if(r<n) q.push(st(l,r+1,c+2));
  }
  //cout<<dp[0][n]<<endl;
  memset(used2,0,sizeof(used2));
  dfs(0,n);
  //cout<<(int)dp2[0][n]<<endl;
  if(dp2[0][n]<K){
    cout<<"NONE"<<endl;
    return 0;
  }
  dfs2(0,n,K);
  return 0;
}
```