Migrated from Lutece 2828 子串排序

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

ljj 实在是懒得编题面了，但他还是想问你这样一个问题：

给你一个长度为 $n$ 的字符串 $s$，问它的第 $k$ 小的子串是什么？

同时还要输入一个数 $t$，如果 $t=0$ 把不同位置的相同子串算作一个，如果 $t=1$ 把不同位置的相同子串算作多个

如果这个串存在，把这个串输出出来，否则输出 -1

Input

第一行输入字符串 $s$

第二行读入两个整数 $t,k$，含义如题目所示

Output

输出一行表示第 $k$ 小的字符串

Samples

aaabbc
0 10

ab

aaabbc
1 10

aab

aaabbc
1 100

-1

Constraints

$n\le 5\times 10^{5},t=\{0,1\},1\le k\le 10^{9}$

Resources

2022 UESTC ICPC Training for String and Search Algorithm