Description:


对于一个给定长度为N的字符串,求它的第K小子串是什么。

Input:


第一行是一个仅由小写英文字母构成的字符串S
第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output:


输出仅一行,为一个数字串,为第K小的子串。如果子串数目不足K个,则输出-1

Sample Input:


Sample Output:


HINT:


 N<=5*10^5,T<2,K<=10^9

题解:


之前对后缀自动机一无所知,表示只会构造。
看到这道题目想了半天后仍然没有思路,然而题解上说这是裸题(好吧我不会用后缀自动机)
\(T = 0\) 时,我们把除了1号节点的点的权值赋为1;
\(T = 1\) 时,我们把除了1号节点的点的权值赋为其fail子树中结束节点个数。
然后算一下。