406902: GYM102606 I Idiotic Suffix Array

Cuber QQ did not know about the Suffix Array before, now he knows. So he eagerly wants to teach you.

Now he takes a string containing only lowercase letters as an example and builds a Suffix Array with the following C++ code on a supercomputer.

std::vector<size_t> build(const std::string& s) {
    std::vector<std::pair<std::string, size_t> > suffixes;
    for (size_t i = 0; i < s.length(); ++i) {
        suffixes.emplace_back(s.substr(i), i);
    }
    std::sort(suffixes.begin(), suffixes.end());
    std::vector<size_t> sa(s.length());
    for (size_t i = 0; i < s.length(); ++i) {
        sa[i] = suffixes[i].second;
    }
    return sa;
}

For example, the Suffix Array of "ecnu" is $$$\{1, 0, 2, 3\}$$$ and the Suffix Array of "cubercsl" is $$$\{2, 5, 0, 3, 7, 4, 6, 1\}$$$.

It's definitely not satisfying enough for Cuber QQ to show off his algorithm skills, so he wants to test you with a problem.

He will give you two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n$$$), you are required to answer him a string of length $$$n$$$ containing only lowercase letters and satisfying sa[k - 1] == 0, where sa is the Suffix Array of the string built by the code above.

TL;DR, you are required to answer a string of length $$$n$$$ containing only lowercase letters and it ranks $$$k$$$-th smallest among all its suffixes in lexicographical order.

We can show that an answer always exists.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

• $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
• in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Two integers $$$n$$$, $$$k$$$ ($$$1 \leq k \leq n \leq 10 ^ 5$$$) — the length of the string and the rank of the string itself among all its suffixes.

Output the answer, which is a string of length $$$n$$$ only containing lowercase letters.

If there are multiple answers, print any of them.

4 2

ecnu

8 3

cubercsl