题目描述

文字列 $s$ が与えられます。 $s$ の異なる substring のうち、辞書順で $K$ 番目に小さいものを出力してください。

ただし、$s$ の substring とは、 $s$ の空でない連続した部分を取り出してできる文字列とします。 例えば、 $s$ $=$ ababc とすると、 a, bab, ababc は $s$ の substring ですが、 ac, z, 空文字列 は $s$ の substring ではありません。 また、substring が異なるとは、文字列として異なることを指します。

なお、$X\ =\ x_{1}x_{2}...x_{n},$ $Y\ =\ y_{1}y_{2}...y_{m}$ を二つの異なる文字列とするとき、$Y$ が $X$ の接頭辞であるか、$j$ を $x_{j}\ \neq\ y_{j}$ であるような最小の整数として $x_{j}\ >\ y_{j}$ である場合、そしてその場合に限って $X$ は $Y$ より辞書順で大きいといいます。

输入格式

入力は以下の形式で標準入力から与えられる。

$s$ $K$

输出格式

辞書順で $K$ 番目に小さい $s$ の substring を出力せよ。

题目大意

Description

给定一个字符串 $S$，在 $S$ 的所有 互不相同的 非空字串中找出其中找到字典序第 $K$ 小的字串并输出。换句话说，就是找出 $S$ 所有的非空字串，按字典序升序排序， 去重 后再选出第 $K$ 个。

Input

第一行，一个字符串 $S$ ；

第二行，一个整数 $K$ 。

Output

一个字符串表示答案。

Hint

• $1\le |S|\le 5\times 10^3$

• $K\in [1,5]$

其中 $S$ 只含有小写字母，保证 $S$ 中含有 $K$ 个不同的非空字串。

Translated by @_Wallace_

aba
4

b

atcoderandatcodeer
5

andat

z
1

z

提示

制約

• $1$ $<\ =$ $|s|$ $<\ =$ $5000$
• $s$ は英小文字からなる
• $1$ $<\ =$ $K$ $<\ =$ $5$
• $s$ は異なる substring を $K$ 個以上持つ

部分点

• $|s|$ $<\ =$ $50$ を満たすデータセットに正解した場合は、部分点として $200$ 点が与えられる。

Sample Explanation 1

$s$ の substring は a, b, ab, ba, aba の $5$ つです。 このうち $4$ 番目に小さい b を出力してください。 a を $2$ 回カウントしないことに注意してください。