#include <iostream>
#include <cassert>
#define ll long long
// 팰린드롬은 결국 문자 2개의 매칭의 연속이다.
// 결국 요문제는 valid한 매칭을 최대화 시켜서
// 매칭에 포함되지 않는 문자를 최소화 시키는 문제로 바꿔 풀 수 있다.
using namespace std;
const ll MAXN = 2005;
pair<ll,ll> dp[MAXN][MAXN]; ll k,n; ll vis[MAXN][MAXN],lt,rt;
string s;
void better(pair<ll,ll> &dp1,pair<ll,ll> dp2){
    if(dp1.first > dp2.first) dp1 = dp2;
    else if(dp1.first == dp2.first) dp1.second += dp2.second;
    if(dp1.second > 2e18){
        dp1.second = 2e18;
    }
}
pair<ll,ll> go(ll l,ll r){
    if(vis[l][r]) return dp[l][r];
    vis[l][r] = 1;
    dp[l][r] = make_pair(1e9,0);
    if(l >= r)return dp[l][r] = make_pair(0,1);
    if(s[l] == s[r]) better(dp[l][r],go(l+1,r-1));
    else{
        pair<ll,ll> t = go(l+1,r); t.first++;
        better(dp[l][r],t);
        t = go(l,r-1); t.first++;
        better(dp[l][r],t);
    }
    return dp[l][r];
}
void make(int l,int r,string &ans,long long K){
    if(lt > rt)return;
    if(l == 0 && r == n && dp[l][r].second < k){
        ans.clear(); ans = "NONE"; return;
    }
    if(s[l] == s[r]){
        ans[lt++] = s[l]; ans[rt--] = s[l];
        make(l+1,r-1,ans,K);
    }
    else if(dp[l+1][r].first > dp[l][r-1].first){
        ans[lt++] = s[r]; ans[rt--] = s[r];
        make(l,r-1,ans,K);
    }
    else if(dp[l][r-1].first > dp[l+1][r].first){
        ans[lt++] = s[l]; ans[rt--] = s[l];
        make(l+1,r,ans,K);
    }
    else{
        if(s[l] == s[r]){
            ans[lt++] = s[l]; ans[rt--] = s[r];
            make(l+1,r-1,ans,K);
        }
        if(s[l] < s[r]){
            if(dp[l+1][r].second >= K){
                ans[lt++] = s[l]; ans[rt--] = s[l];
                make(l+1,r,ans,K);
            }
            else{
                K -= dp[l+1][r].second;
                ans[lt++] = s[r]; ans[rt--] = s[r];
                make(l,r-1,ans,K);
            }
        }
        if(s[l] > s[r]){
            if(dp[l][r-1].second >= K){
                ans[lt++] = s[r]; ans[rt--] = s[r];
                make(l,r-1,ans,K);
            }
            else{
                K -= dp[l][r-1].second;
                ans[lt++] = s[l]; ans[rt--] = s[l];
                make(l+1,r,ans,K);
            }
        }
    }
}
int main(){
    
    
    cin>>s>>k;
    n = s.length(); n--;
    pair<ll,ll> d = go(0,n);
    ll add = d.first;
    string ans; ans.resize(s.length() + add,'a');
    lt = 0; rt = ans.size()-1;
    make(0,n,ans,k);
    cout<<ans<<endl;
    
    return 0;
}


### Prompt

Develop a solution in Cpp to the problem described below:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <iostream>
#include <cassert>
#define ll long long
// 팰린드롬은 결국 문자 2개의 매칭의 연속이다.
// 결국 요문제는 valid한 매칭을 최대화 시켜서
// 매칭에 포함되지 않는 문자를 최소화 시키는 문제로 바꿔 풀 수 있다.
using namespace std;
const ll MAXN = 2005;
pair<ll,ll> dp[MAXN][MAXN]; ll k,n; ll vis[MAXN][MAXN],lt,rt;
string s;
void better(pair<ll,ll> &dp1,pair<ll,ll> dp2){
    if(dp1.first > dp2.first) dp1 = dp2;
    else if(dp1.first == dp2.first) dp1.second += dp2.second;
    if(dp1.second > 2e18){
        dp1.second = 2e18;
    }
}
pair<ll,ll> go(ll l,ll r){
    if(vis[l][r]) return dp[l][r];
    vis[l][r] = 1;
    dp[l][r] = make_pair(1e9,0);
    if(l >= r)return dp[l][r] = make_pair(0,1);
    if(s[l] == s[r]) better(dp[l][r],go(l+1,r-1));
    else{
        pair<ll,ll> t = go(l+1,r); t.first++;
        better(dp[l][r],t);
        t = go(l,r-1); t.first++;
        better(dp[l][r],t);
    }
    return dp[l][r];
}
void make(int l,int r,string &ans,long long K){
    if(lt > rt)return;
    if(l == 0 && r == n && dp[l][r].second < k){
        ans.clear(); ans = "NONE"; return;
    }
    if(s[l] == s[r]){
        ans[lt++] = s[l]; ans[rt--] = s[l];
        make(l+1,r-1,ans,K);
    }
    else if(dp[l+1][r].first > dp[l][r-1].first){
        ans[lt++] = s[r]; ans[rt--] = s[r];
        make(l,r-1,ans,K);
    }
    else if(dp[l][r-1].first > dp[l+1][r].first){
        ans[lt++] = s[l]; ans[rt--] = s[l];
        make(l+1,r,ans,K);
    }
    else{
        if(s[l] == s[r]){
            ans[lt++] = s[l]; ans[rt--] = s[r];
            make(l+1,r-1,ans,K);
        }
        if(s[l] < s[r]){
            if(dp[l+1][r].second >= K){
                ans[lt++] = s[l]; ans[rt--] = s[l];
                make(l+1,r,ans,K);
            }
            else{
                K -= dp[l+1][r].second;
                ans[lt++] = s[r]; ans[rt--] = s[r];
                make(l,r-1,ans,K);
            }
        }
        if(s[l] > s[r]){
            if(dp[l][r-1].second >= K){
                ans[lt++] = s[r]; ans[rt--] = s[r];
                make(l,r-1,ans,K);
            }
            else{
                K -= dp[l][r-1].second;
                ans[lt++] = s[l]; ans[rt--] = s[l];
                make(l+1,r,ans,K);
            }
        }
    }
}
int main(){
    
    
    cin>>s>>k;
    n = s.length(); n--;
    pair<ll,ll> d = go(0,n);
    ll add = d.first;
    string ans; ans.resize(s.length() + add,'a');
    lt = 0; rt = ans.size()-1;
    make(0,n,ans,k);
    cout<<ans<<endl;
    
    return 0;
}


```