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 翻译