弦论

题目描述

小兰刚学数据结构算法，现在学到了字符串的相关算法，她想学习弦论来增加自己对字符串相关算法的理解。她在《String theory》中看到了这样有关字符串算法的问题：对于一个给定的长度为n的字符串，求出它的第k小的子串是什么。请编写一个程序帮助小兰。

输入

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

输出

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

样例

提示

【数据范围】
对于 30% 的数据，n ≤1000 。
对于 50% 的数据，t = 0。
对于 100% 的数据，1 ≤ n ≤ 5 × 105 ，0 ≤ t ≤ 1， 1 ≤ k ≤ 10^9。