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

using ll = long long;

constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;

ll add(ll& a, ll b) {
    return a = min(a + b, INFLL * 2);
}

int main() {
    string S;
    ll K;
    cin >> S >> K;
    int const n = S.size();
    vector<vector<int>> len(n, vector<int>(n, INF));
    for(int i = n - 1; i >= 0; --i) {
        len[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                len[i][j] = (i + 1 == j ? 2 : len[i + 1][j - 1] + 2);
            }
            len[i][j] = min(len[i][j], min(len[i + 1][j], len[i][j - 1]) + 2);
        }
    }
    vector<vector<ll>> dp(n, vector<ll>(n));
    for(int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                add(dp[i][j], (i + 1 == j ? 1 : dp[i + 1][j - 1]));
            } else {
                int min_len = min(len[i + 1][j], len[i][j - 1]);
                if(len[i + 1][j] == min_len) {
                    add(dp[i][j], dp[i + 1][j]);
                }
                if(len[i][j - 1] == min_len) {
                    add(dp[i][j], dp[i][j - 1]);
                }
            }
        }
    }

    if(dp[0][n - 1] < K) {
        cout << "NONE" << endl;
        return 0;
    }

    ll t = 1;
    string l_ans;
    int l = 0, r = n - 1;
    while(l < r) {
        if(S[l] == S[r]) {
            l_ans += S[l++];
            r--;
        } else {
            if(len[l + 1][r] < len[l][r - 1]) {
                l_ans += S[l++];
            } else if(len[l + 1][r] > len[l][r - 1]) {
                l_ans += S[r--];
            } else {
                ll t2 = t + (S[l] < S[r] ? dp[l + 1][r] : dp[l][r - 1]);
                if(t2 > K && S[l] < S[r] || t2 <= K && S[l] > S[r]) {
                    l_ans += S[l++];
                } else {
                    l_ans += S[r--];
                }
                if(t2 <= K) {
                    t = t2;
                }
            }
        }
    }
    auto r_ans = l_ans;
    reverse(begin(r_ans), end(r_ans));
    if(l == r) {
        l_ans += S[l];
    }
    cout << l_ans + r_ans << endl;
}

### Prompt

Construct a CPP code solution to the problem outlined:

Example

Input

crc
1


Output

crc

### Response

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

using ll = long long;

constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;

ll add(ll& a, ll b) {
    return a = min(a + b, INFLL * 2);
}

int main() {
    string S;
    ll K;
    cin >> S >> K;
    int const n = S.size();
    vector<vector<int>> len(n, vector<int>(n, INF));
    for(int i = n - 1; i >= 0; --i) {
        len[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                len[i][j] = (i + 1 == j ? 2 : len[i + 1][j - 1] + 2);
            }
            len[i][j] = min(len[i][j], min(len[i + 1][j], len[i][j - 1]) + 2);
        }
    }
    vector<vector<ll>> dp(n, vector<ll>(n));
    for(int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                add(dp[i][j], (i + 1 == j ? 1 : dp[i + 1][j - 1]));
            } else {
                int min_len = min(len[i + 1][j], len[i][j - 1]);
                if(len[i + 1][j] == min_len) {
                    add(dp[i][j], dp[i + 1][j]);
                }
                if(len[i][j - 1] == min_len) {
                    add(dp[i][j], dp[i][j - 1]);
                }
            }
        }
    }

    if(dp[0][n - 1] < K) {
        cout << "NONE" << endl;
        return 0;
    }

    ll t = 1;
    string l_ans;
    int l = 0, r = n - 1;
    while(l < r) {
        if(S[l] == S[r]) {
            l_ans += S[l++];
            r--;
        } else {
            if(len[l + 1][r] < len[l][r - 1]) {
                l_ans += S[l++];
            } else if(len[l + 1][r] > len[l][r - 1]) {
                l_ans += S[r--];
            } else {
                ll t2 = t + (S[l] < S[r] ? dp[l + 1][r] : dp[l][r - 1]);
                if(t2 > K && S[l] < S[r] || t2 <= K && S[l] > S[r]) {
                    l_ans += S[l++];
                } else {
                    l_ans += S[r--];
                }
                if(t2 <= K) {
                    t = t2;
                }
            }
        }
    }
    auto r_ans = l_ans;
    reverse(begin(r_ans), end(r_ans));
    if(l == r) {
        l_ans += S[l];
    }
    cout << l_ans + r_ans << endl;
}

```