Hth Number

Time Limit : 3 sec, Memory Limit : 524288 KB

Problem H: Hth Number

Problem

長さ$N$の文字列$S$がある。$S$に含まれる文字はすべて0以上9以下の数字である。
$S$のすべての部分文字列から作られる数を全列挙してできた項数$\frac{N\times(N+1)}{2}$の数列を作った時、 その数列の中で$H$番目に小さい値を求めよ。

Input

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

$N$ $H$
$S$

入力はすべて整数で与えられる。
1行目に$N$と$H$が空白区切りで与えられる。
2行目に長さ$N$の文字列$S$が与えられる。

Constraints

入力は以下の条件を満たす。

  • $1 \leq N \leq 10^5$
  • $1 \leq H \leq \frac{N \times (N+1)}{2}$
  • $|S| = N$
  • $S$に含まれる文字はすべて0, 1, 2, 3, 4, 5, 6, 7, 8, 9のいずれかである

Output

$H$番目の値を1行に出力せよ。
(出力の先頭に余計な0は含んではならない。)

Sample Input 1

2 3
00

Sample Output 1

0

Sample Input 2

4 9
0012

Sample Output 2

12

Sample Input 3

5 13
10031

Sample Output 3

100

Sample Input3の場合、10031の部分文字列から作られる数は以下の通りである。
1, 0, 0, 3, 1
10, 00, 03, 31
100, 003, 031
1003, 0031
10031
これらをを小さい順に並べると 0, 0, 0, 1, 1, 3, 3, 3, 10, 31, 31, 31, 100, 1003, 10031 になり、13番目に小さい値は100である。