[TJOI2015]弦论

题目描述

为了提高智商,ZJY 开始学习弦论。这一天,她在《String theory》中看到了这样一道问题:对于一个给定的长度为 $n$ 的字符串,求出它的第 $k$ 小子串是什么。你能帮帮她吗?

输入输出格式

输入格式


第一行是一个仅由小写英文字母构成的字符串 $s$。 第二行为两个整数 $t$ 和 $k$,$t$ 为 $0$ 则表示不同位置的相同子串算作一个,$t$ 为 $1$ 则表示不同位置的相同子串算作多个。$k$ 的意义见题目描述。

输出格式


输出数据仅有一行,该行有一个字符串,为第 $k$ 小的子串。若子串数目不足 $k$ 个,则输出 $-1$。

输入输出样例

输入样例 #1

aabc
0 3

输出样例 #1

aab

输入样例 #2

aabc
1 3

输出样例 #2

aa

输入样例 #3

aabc
1 11

输出样例 #3

-1

说明

### 数据范围 对于 $10\%$ 的数据,$n\leq 1000$。 对于 $50\%$ 的数据,$t = 0$。 对于 $100\%$ 的数据,$1\leq n \leq 5 \times 10^5$,$0\leq t \leq 1$,$1\leq k \leq 10^9$。