该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给出一个字符\(S\)，求其第\(k\)小子串。这里的大小即指字典序。

Format

Input

每个测试点仅包含一组输入数据。
第一行一个仅由小写英文字母组成的字符串\(S(|S|<=500000)\)。
第二行两个整数\(T(T=0,1),K(1<=K<=10^9)\)。
若\(T=0\)，则表示不同位置的相同子串算作一个，若\(T=1\)，则表示不同位置的相同子串算作多个。

Output

输出一行一个字符串，为答案。若子串数量不足\(k\)个，则输出\(-1\)。

Sample 1

Input

aabc
0 3

Output

aab

Limitation

1s, 1GB for each test case.

Source

Vijos Original