P3975 [TJOI2015] String Theory

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?

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 exactly one line containing a string, which is the $k$-th smallest substring. If there are fewer than $k$ substrings, output -1.

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