Description

To boost her IQ, ZJY started studying string theory. One day, she saw the following problem in "String theory": Given a string of length $n$, find its $k$-th smallest substring. Can you help her?

Input Format

The first line contains a string $s$ consisting only of lowercase English letters.

The second line contains two integers $t$ and $k$. If $t = 0$, identical substrings at different positions are counted as one; if $t = 1$, identical substrings at different positions are counted multiple times. The meaning of $k$ is as described above.

Output Format

Output exactly one line containing a string, which is the $k$-th smallest substring. If there are fewer than $k$ substrings, output -1.

aabc
0 3

aab

aabc
1 3

aa

aabc
1 11

-1

Hint

Constraints

For $10\%$ of the testdata, $n\leq 1000$.

For $50\%$ of the testdata, $t = 0$.

For $100\%$ of the testdata, $1\leq n \leq 5 \times 10^5$, $0\leq t \leq 1$, $1\leq k \leq 10^9$.

Translated by ChatGPT 5