/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
整数 N,K と長さ N の英小文字からなる文字列 S が与えられます。 S の \displaystyle \frac{N(N+1)}2 個の非空な連続部分文字列を辞書順に並べた時、小さい方から K 番目の文字列を求めてください。
制約
- 1\le N\le 10^6
- \displaystyle 1\le K\le \frac{N(N+1)}2
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
答えを出力せよ。
入力例 1
3 3 aba
出力例 1
ab
S= aba の非空な部分文字列は a, ab, aba, b, ba, a の 6 個で、これらを辞書順に並べると a, a, ab, aba, b, ba となります。小さい方から 3 番目は ab なので、 ab を出力してください。
入力例 2
5 8 wwwww
出力例 2
ww
入力例 3
8 28 chokudai
出力例 3
ok
入力例 4
22 30 atcoderbeginnercontest
出力例 4
beginner
Problem Statement
You are given integers N and K, and a length-N string S consisting of lowercase English letters. When the \displaystyle \frac{N(N+1)}2 nonempty contiguous substrings of S are arranged in lexicographical order, find the K-th smallest string.
Constraints
- 1\le N\le 10^6
- \displaystyle 1\le K\le \frac{N(N+1)}2
- S is a string of length N consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N K S
Output
Print the answer.
Sample Input 1
3 3 aba
Sample Output 1
ab
The nonempty substrings of S= aba are these six: a, ab, aba, b, ba, a. In lexicographical order, they are a, a, ab, aba, b, ba. Print the 3-rd smallest string ab.
Sample Input 2
5 8 wwwww
Sample Output 2
ww
Sample Input 3
8 28 chokudai
Sample Output 3
ok
Sample Input 4
22 30 atcoderbeginnercontest
Sample Output 4
beginner