#P18330. Divide Digit String

Divide Digit String

Divide Digit String

给定一个长度为 NN、只由数字 1 到 9 组成的数字串 SS,以及整数 M,KM,K,满足 1≤K≤M≤N1\le K\le M\le N。

你需要将 SS 分成 MM 个非空的连续子串,并将每个子串看作一个十进制整数。

在所有分割方式中,求这 MM 个整数的第 KK 大可能达到的最小值。

共有 TT 组测试用例,请分别求解。

输入格式

第一行包含一个整数 TT。

接下来依次给出 TT 组测试用例,每组格式如下:

N M K
S

输出格式

输出 TT 行。第 ii 行输出第 ii 组测试用例的答案。

数据范围

  • 1≤T≤1051\le T\le10^5;
  • 1≤K≤M≤N≤1061\le K\le M\le N\le10^6;
  • SS 长度为 NN,只包含数字 1 到 9;
  • 所有测试用例的 NN 之和不超过 10610^6;
  • T,N,M,KT,N,M,K 均为整数。

样例输入 1

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

样例输出 1

123
1
26

样例说明

第一组中,将 SS 分为 123 和 45,最大整数为 123123,这是最大整数可能达到的最小值。

第二组中,将 SS 分为 1、23 和 45,第三大的整数为 11,这是第三大整数可能达到的最小值。