Example

Input

crc
1


Output

crc
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll INF=1e18l+5;

int main(){
    string s;
    cin>>s;
    ll k;
    cin>>k;
    k--;
    int n=s.size();
    vector<vector<ll>> dp(n,vector<ll>(n+1,1));
    vector<vector<ll>> dpl(n,vector<ll>(n+1,1));
    for(int i=0;i<n;i++) dpl[i][i]=0,dpl[i][i+1]=1;
    for(int span=2;span<=n;span++){
        for(int i=0;i+span<=n;i++){
            int j=i+span;
            if(s[i]==s[j-1]) dp[i][j]=dp[i+1][j-1],dpl[i][j]=dpl[i+1][j-1]+2;
            else{
                if(dpl[i+1][j]<dpl[i][j-1]){
                    dpl[i][j]=dpl[i+1][j]+2;
                    dp[i][j]=dp[i+1][j];
                }
                else if(dpl[i+1][j]>dpl[i][j-1]){
                    dpl[i][j]=dpl[i][j-1]+2;
                    dp[i][j]=dp[i][j-1];
                }
                else{
                    dpl[i][j]=dpl[i][j-1]+2;
                    dp[i][j]=min(dp[i][j-1]+dp[i+1][j],INF);
                }
            }
        }
    }
    int i=0,j=n;
    string fr,bk;
    while(j-i>1){
        if(s[i]==s[j-1]){
            fr+=s[i],i=i+1; 
            bk+=s[j-1],j=j-1; 
        }
        else{
            if(dpl[i+1][j]==dpl[i][j-1]){
                if(s[j-1]<s[i]){
                    if(k>=dp[i][j-1]){
                        k-=dp[i][j-1];
                        fr+=s[i],bk+=s[i],i++;
                    }
                    else{
                        fr+=s[j-1],bk+=s[j-1],j=j-1;
                    }
                }
                else{
                    if(k>=dp[i+1][j]){
                        k-=dp[i+1][j];
                        fr+=s[j-1],bk+=s[j-1],j--;
                    }
                    else{
                        fr+=s[i],bk+=s[i],i++;
                    }
                }
            }
            else{
                if(dpl[i+1][j]<dpl[i][j-1]){
                    fr+=s[i],bk+=s[i],i++;
                }   
                else{
                    fr+=s[j-1],bk+=s[j-1],j--;
                }
            }
        }
    }
    if(j-i)  fr+=s[i],i++;
    reverse(bk.begin(),bk.end());
    if(k){
        cout<<"NONE"<<endl;
    }
    else{
        cout<<fr<<bk<<endl;
    }

    return 0;
}
