Migrated from Lutece 3061 kth substring

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一个长度为 $N$ 的字符串 $S$，求它的第 $K$ 小子串。

Input

第一行为字符串 $S$，保证仅由小写英文字母构成；

第二行为两个整数 $T$ 和 $K$，其中：

$T=0$ 表示不同位置的相同子串算作一个，$T=1$ 则表示不同位置的相同子串算作多个。$K$ 的意义如题所述。

Output

一行一个小写英文字母构成的字符串表示第 $K$ 小的子串。如果子串数目不足 $K$ 个，则输出 $-1$。

Samples

aabc
0 3

aab

aabaa
1 5

aa

Constraints

$N\leq 5 \times 10^5$ $T\in\{0,1\}$ $K\leq 10^9$

Resources

2023 UESTC ICPC Training for String