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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define rrep(i, j) for(int i=(j-1); i>=0; i--)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1e18 * 4;

void add_limited(ll &a, const ll &b) { a = a + b > INFL ? INFL : a + b; }

class Solver {
  public:
    
    bool solve() {
        string S; cin >> S;
        ll K; cin >> K;
        int N = S.size();        
        vector<vector<int>> dp(N, vector<int>(N, INF));
        //
        // dp[i][j] (i < j) := s[i]...s[j] ???????????????????°????????????????        
        //
        rrep(i, N) {
            repeat(j, i, N) {
                if(i == j) {
                    dp[i][j] = 1;
                } else {
                    if(S[i] == S[j]) dp[i][j] = (i + 1 == j ? 0 : dp[i + 1][j - 1]); 
                    dp[i][j] = min({ dp[i][j], dp[i + 1][j], dp[i][j - 1] });
                    dp[i][j] += 2;
                }
            }
        }
        // cerr << "SCS " << dp[0][N - 1] << endl;

        //
        // dp2[i][j] (i < j) := s[i]..s[j] ???????????????????°???????????????????????????°
        //
        vector<vector<ll>> dp2(N, vector<ll>(N, 0));
        rrep(i, N) {
            repeat(j, i, N) {
                if(i == j) {
                    dp2[i][j] = 1;
                } else {
                    if(S[i] == S[j]) {
                        add_limited(dp2[i][j], (i + 1 == j ? 1 : dp2[i + 1][j - 1]));
                    } else {
                        ll mini = min({dp[i + 1][j], dp[i][j - 1] });
                        if(dp[i + 1][j] == mini) add_limited(dp2[i][j], dp2[i + 1][j]);
                        if(dp[i][j - 1] == mini) add_limited(dp2[i][j], dp2[i][j - 1]);                        
                    }
                }
            }
        }
        // debug(dp2);

        if(dp2[0][N - 1] < K) {
            cout << "NONE" << endl;
            return 0;
        }
        
        //
        // K???????????????????????????????????????        
        //
        
        ll cnt = 1;
        string ans = "";
        int i = 0, j = N - 1;

        auto next_i = [&](bool add = true) {
            if(add) ans += S[i];
            i++;            
        };
        auto next_j = [&](bool add = true) {
            if(add) ans += S[j];
            j--;
        };
        while(i < j) {
            if(S[i] == S[j]) {
                next_i();
                next_j(false);
            } else {
                // 1 : i+1, j-1 ??§???????????????????????????????????¶??§?°???????????????????
                // 2 : ????????????, ?°??????????????????????????????°????¶?????????????
                //     K ????¶??????????????°???????????????????
                //     K ????¶???????????????? ?¶???????????????§??????????????????
                if(dp[i + 1][j] < dp[i][j - 1]) {
                    next_i();
                } else if(dp[i + 1][j] > dp[i][j - 1]) {
                    next_j();
                } else {
                    assert(dp[i + 1][j] == dp[i][j - 1]);
                    
                    ll nxt_cnt = cnt + (S[i] < S[j] ? dp2[i + 1][j] : dp2[i][j - 1]);
                    if(nxt_cnt > K) {
                        if(S[i] < S[j]) next_i();
                        else next_j();
                    } else {
                        cnt = nxt_cnt;
                        if(S[i] < S[j]) next_j();
                        else next_i();
                    }
                }
            }
        }
        string rans = ans;        
        reverse(all(rans));
        cout << ans + (i == j ? S.substr(i, 1) : "") + rans << endl;
        
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}
### Prompt

Develop a solution in CPP to the problem described below:

Example

Input

crc
1


Output

crc

### Response

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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define rrep(i, j) for(int i=(j-1); i>=0; i--)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1e18 * 4;

void add_limited(ll &a, const ll &b) { a = a + b > INFL ? INFL : a + b; }

class Solver {
  public:
    
    bool solve() {
        string S; cin >> S;
        ll K; cin >> K;
        int N = S.size();        
        vector<vector<int>> dp(N, vector<int>(N, INF));
        //
        // dp[i][j] (i < j) := s[i]...s[j] ???????????????????°????????????????        
        //
        rrep(i, N) {
            repeat(j, i, N) {
                if(i == j) {
                    dp[i][j] = 1;
                } else {
                    if(S[i] == S[j]) dp[i][j] = (i + 1 == j ? 0 : dp[i + 1][j - 1]); 
                    dp[i][j] = min({ dp[i][j], dp[i + 1][j], dp[i][j - 1] });
                    dp[i][j] += 2;
                }
            }
        }
        // cerr << "SCS " << dp[0][N - 1] << endl;

        //
        // dp2[i][j] (i < j) := s[i]..s[j] ???????????????????°???????????????????????????°
        //
        vector<vector<ll>> dp2(N, vector<ll>(N, 0));
        rrep(i, N) {
            repeat(j, i, N) {
                if(i == j) {
                    dp2[i][j] = 1;
                } else {
                    if(S[i] == S[j]) {
                        add_limited(dp2[i][j], (i + 1 == j ? 1 : dp2[i + 1][j - 1]));
                    } else {
                        ll mini = min({dp[i + 1][j], dp[i][j - 1] });
                        if(dp[i + 1][j] == mini) add_limited(dp2[i][j], dp2[i + 1][j]);
                        if(dp[i][j - 1] == mini) add_limited(dp2[i][j], dp2[i][j - 1]);                        
                    }
                }
            }
        }
        // debug(dp2);

        if(dp2[0][N - 1] < K) {
            cout << "NONE" << endl;
            return 0;
        }
        
        //
        // K???????????????????????????????????????        
        //
        
        ll cnt = 1;
        string ans = "";
        int i = 0, j = N - 1;

        auto next_i = [&](bool add = true) {
            if(add) ans += S[i];
            i++;            
        };
        auto next_j = [&](bool add = true) {
            if(add) ans += S[j];
            j--;
        };
        while(i < j) {
            if(S[i] == S[j]) {
                next_i();
                next_j(false);
            } else {
                // 1 : i+1, j-1 ??§???????????????????????????????????¶??§?°???????????????????
                // 2 : ????????????, ?°??????????????????????????????°????¶?????????????
                //     K ????¶??????????????°???????????????????
                //     K ????¶???????????????? ?¶???????????????§??????????????????
                if(dp[i + 1][j] < dp[i][j - 1]) {
                    next_i();
                } else if(dp[i + 1][j] > dp[i][j - 1]) {
                    next_j();
                } else {
                    assert(dp[i + 1][j] == dp[i][j - 1]);
                    
                    ll nxt_cnt = cnt + (S[i] < S[j] ? dp2[i + 1][j] : dp2[i][j - 1]);
                    if(nxt_cnt > K) {
                        if(S[i] < S[j]) next_i();
                        else next_j();
                    } else {
                        cnt = nxt_cnt;
                        if(S[i] < S[j]) next_j();
                        else next_i();
                    }
                }
            }
        }
        string rans = ans;        
        reverse(all(rans));
        cout << ans + (i == j ? S.substr(i, 1) : "") + rans << endl;
        
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}
```