Description

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?

Input Format

• 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 Format

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

3 3
abb

abb

3 5
abb

bb

Hint

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