P3728 Manhattan Sequence

To study the problem of computing the Manhattan distance between two points as the final output in a "dynamic cactus graph" using a branch-and-bound heuristic based on operation-order divide-and-conquer with blossom-tree bounds, maintained by a fully persistent suffix global balanced tree, will needs to generate some letter sequences. During the process of writing the generator, because will is too weak, he encountered some problems. Now, he needs your help to solve them.

The sequence generator works as follows: - will first fixes a mother sequence of length $N$, consisting of lowercase letters. - A subsequence is defined as a non-empty sequence obtained by deleting zero or more characters at arbitrary positions from the mother sequence. For example: "a b" and "a c" are subsequences of "a b c", but "c a" is not. - Obviously, a sequence of length $N$ has $2^N - 1$ subsequences. - Sort these $2^N - 1$ subsequences in lexicographical order. will will generate subsequences in this order. - will wants to remove duplicate subsequences. If several subsequences are identical (i.e., equal in lexicographical order), only one is generated. - Now, he wants to know: what is the subsequence generated on the $K$-th time?

- The first line contains two positive integers $N$, $K$. $N$ is the length of the mother sequence, and $K$ is the query. - The second line contains $N$ lowercase letters, representing the mother sequence.

Output one line consisting of lowercase letters: the subsequence generated on the $K$-th time.

Sample Explanation: For the mother sequence "a b b", there are 7 subsequences, sorted in lexicographical order: - a. - a b. - a b. - a b b. - b. - b. - b b. After removing duplicates, the 3rd one is "a b b". Constraints: - For 20% of the testdata, $N \leq 15$. - For 50% of the testdata, $N \leq 1000$. - For 80% of the testdata, $N \leq 200000$. - For 100% of the testdata, $N \leq 1000000$, $K \leq 10^9$, and it is guaranteed that the $K$-th output exists. - The time limit for the first 80% of the testdata is 1 s, and for the last 20% of the testdata is 2 s. Translated by ChatGPT 5