Problem Description

To enhance her intelligence, ZJY starts learning string theory. On this day, she encountered a problem in "String Theory": for a given string of length $n$, find its $k$-th smallest substring. Can you help her with this?

Input Format

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

The second line contains two integers $t$ and $k$. If $t$ is $0$, identical substrings at different positions are considered as one. If $t$ is $1$, identical substrings at different positions are considered as multiple. The meaning of $k$ is described in the problem statement.

Output Format

The output consists of a single line, which contains the $k$-th smallest substring. If there are fewer than $k$ substrings, output $-1$.

Sample Input and Output

Sample Input #1

aabc
0 3

Sample Output #1

aab

Sample Input #2

aabc
1 3

Sample Output #2

aa

Sample Input #3

aabc
1 11

Sample Output #3

-1

Notes

Data Range

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

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

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

见题面 Input 部分

见题面 Output 部分