M - Divide Digit String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : {100} 点

問題文

1 から 9 までの数字からなる長さ N の数字列 S と整数 M,K(1\leq K\leq M\leq N) が与えられます。

S を M 個の非空な数字列に分割してそれぞれを 10 進法の整数とみなします。これら M 個の整数のうち大きい方から K 番目のものとしてあり得る最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

  • 1\leq T\leq 10^5
  • 1\leq K\leq M\leq N\leq 10^6
  • T,N,M,K は整数
  • S は 1 から 9 までの数字からなる長さ N の数字列
  • 1 つの入力ファイルに含まれる N の総和は 10^6 以下

入力

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

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N M K
S

出力

T 行出力せよ。 i 行目には i 個目のテストケースについて、 M 個の整数のうち大きい方から K 番目のものとしてあり得る最小値を出力せよ。

入力例 1

3
5 2 1
12345
5 3 3
12345
10 7 1
3141592653

出力例 1

123
1
26

1 つ目のテストケースについて、 S を \texttt{123},\texttt{45} のように分割することで 1 番目に大きいものが 123 となり、これが最小です。

2 つ目のテストケースについて、 S を \texttt{1},\texttt{23},\texttt{45} のように分割することで 3 番目に大きいものが 1 となり、これが最小です。