Example

Input

crc
1


Output

crc
#include <iostream>
#include <vector>
#include <string>
#include <functional>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

using lint = long long;
constexpr lint INF = 1LL << 60;

lint add(lint a, lint b) { return std::min(a + b, INF); }

void solve() {
    std::string s;
    std::cin >> s;
    int n = s.length();
    s = '$' + s;

    auto ldp = vec(n + 1, vec(n + 1, -1));
    auto pdp = vec(n + 1, vec(n + 1, 0LL));

    for (int len = 0; len <= n; ++len) {
        for (int l = 1; l <= n && l + len - 1 <= n; ++l) {
            int r = l + len - 1;

            if (len <= 1) {
                ldp[l][r] = len;
                pdp[l][r] = 1;
                continue;
            }

            if (s[l] == s[r]) {
                ldp[l][r] = ldp[l + 1][r - 1] + 2;
                pdp[l][r] = pdp[l + 1][r - 1];

            } else {
                if (ldp[l + 1][r] <= ldp[l][r - 1]) {
                    ldp[l][r] = ldp[l + 1][r] + 2;
                    pdp[l][r] = pdp[l + 1][r];

                } else {
                    ldp[l][r] = ldp[l][r - 1] + 2;
                    pdp[l][r] = pdp[l][r - 1];
                }

                if (ldp[l + 1][r] == ldp[l][r - 1]) {
                    pdp[l][r] = add(pdp[l + 1][r], pdp[l][r - 1]);
                }
            }
        }
    }

    bool valid = true;
    std::function<std::string(int, int, lint)>
        dfs = [&](int l, int r, lint k) {
            if (r - l + 1 <= 1) {
                if (k > 0) valid = false;
                return s.substr(l, r - l + 1);
            }

            int nl, nr;
            char c;
            if (s[l] == s[r]) {
                nl = l + 1, nr = r - 1;
                c = s[l];

            } else if (ldp[l + 1][r] < ldp[l][r - 1]) {
                nl = l + 1, nr = r;
                c = s[l];

            } else if (ldp[l + 1][r] > ldp[l][r - 1]) {
                nl = l, nr = r - 1;
                c = s[r];

            } else if (s[l] < s[r]) {
                if (k < pdp[l + 1][r]) {
                    nl = l + 1, nr = r;
                    c = s[l];
                } else {
                    k -= pdp[l + 1][r];
                    nl = l, nr = r - 1;
                    c = s[r];
                }

            } else {
                if (k < pdp[l][r - 1]) {
                    nl = l, nr = r - 1;
                    c = s[r];
                } else {
                    k -= pdp[l][r - 1];
                    nl = l + 1, nr = r;
                    c = s[l];
                }
            }

            auto t = dfs(nl, nr, k);
            return c + t + c;
        };

    lint k;
    std::cin >> k;
    auto ans = dfs(1, n, k - 1);
    std::cout << (valid ? ans : "NONE") << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}

