To improve her IQ, ZJY has started studying string theory. One day, she encountered the following problem in "String Theory": Given a string of length $n$, find its $k$-th smallest substring. Can you help her?
Input
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 as multiple. The meaning of $k$ is as described in the problem statement.
Output
Output a single line containing the $k$-th smallest substring. If there are fewer than $k$ substrings, output $-1$.
Constraints
- For 10% of the data, $n \le 1000$.
- For 50% of the data, $t = 0$.
- For 100% of the data, $n \le 5 \times 10^5$, $t < 2$, $k \le 10^9$.
Examples
Input 1
aabc 0 3
Output 1
aab
Input 2
aabc 1 3
Output 2
aa
Input 3
aabc 1 11
Output 3
-1