[TJOI2015]弦论

题目描述

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

输入格式

第一行是一个仅由小写英文字母构成的字符串 $s$。

第二行为两个整数 $t$ 和 $k$，$t$ 为 $0$ 则表示不同位置的相同子串算作一个，$t$ 为 $1$ 则表示不同位置的相同子串算作多个。$k$ 的意义见题目描述。

输出格式

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

样例 #1

样例输入 #1

aabc
0 3

样例输出 #1

aab

样例 #2

样例输入 #2

aabc
1 3

样例输出 #2

aa

样例 #3

样例输入 #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$。