AT_tupc2024_m Divide Digit String

给定一个由数字 $1$ 到 $9$ 组成、长度为 $N$ 的数字串 $S$，以及两个整数 $M,K$（$1 \leq K \leq M \leq N$）。 请将 $S$ 分成 $M$ 个非空的数字串，并将每个数字串按十进制视为一个整数。在所有可能的分割方案中，求这些 $M$ 个整数中从大到小第 $K$ 大的数的最小可能值。 给定 $T$ 组测试数据，请分别输出答案。

输入按如下格式由标准输入给出。 > $T$ > $\mathrm{case}_1$ > $\vdots$ > $\mathrm{case}_T$ 每组测试数据格式如下： > $N\ M\ K\ S$

输出 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的答案，即将 $S$ 分成 $M$ 个整数后，从大到小第 $K$ 大的数的最小可能值。

### 样例解释 1 对于第 $1$ 组测试数据，将 $S$ 分割为 $\texttt{123},\texttt{45}$，此时第 $1$ 大的数为 $123$，这是可能的最小值。 对于第 $2$ 组测试数据，将 $S$ 分割为 $\texttt{1},\texttt{23},\texttt{45}$，此时第 $3$ 大的数为 $1$，这是可能的最小值。 ### 数据范围 - $1 \leq T \leq 10^5$ - $1 \leq K \leq M \leq N \leq 10^6$ - $T, N, M, K$ 均为整数 - $S$ 是由数字 $1$ 到 $9$ 组成的长度为 $N$ 的数字串 - 每个输入文件中所有测试的 $N$ 之和不超过 $10^6$ 由 ChatGPT 5 翻译