AT_tupc2024_m Divide Digit String

`1` から `9` までの数字からなる長さ $ N $ の数字列 $ S $ と整数 $ M,K(1\leq K\leq M\leq N) $ が与えられます。 $ S $ を $ M $ 個の非空な数字列に分割してそれぞれを $ 10 $ 進法の整数とみなします。これら $ M $ 個の整数のうち大きい方から $ K $ 番目のものとしてあり得る最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ K $ $ S $

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

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、 $ S $ を $ \texttt{123},\texttt{45} $ のように分割することで $ 1 $ 番目に大きいものが $ 123 $ となり、これが最小です。 $ 2 $ つ目のテストケースについて、 $ S $ を $ \texttt{1},\texttt{23},\texttt{45} $ のように分割することで $ 3 $ 番目に大きいものが $ 1 $ となり、これが最小です。 ### Constraints - $ 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 $ 以下