双倍经验。
k>1
首先并不难发现 k>1 的时候答案在 [1,9] 内。
因为显然有一种方案，分 m−1 个长度为 1 的段，剩下的单独成一段，由于 k>1 第 k 大一定长度为 1。
那么考虑枚举答案 ans∈[1,9]。
ans 是第 k 大，相当于是第 m−k+1 小，因此要有 m−k+1 个段是 ≤ans 的。
由于总共要选 m 段，所以还要再选 k−1 段，即我们要求选了上面 m−k+1 段之后，剩余的连通块数量必须 ≤k−1。
考虑 ≤ans 的数组成的连续段，我们需要从这些连续段中挑出 m−k+1 个，并且保证删掉挑出的这些位置之后剩余连通块数量 ≤k−1。
由于最左边和最右边（如果存在）的连续段选了之后不会影响连通块数量，因此可以直接全选。
至于中间的由于要保证剩下 ≤k−1 个连通块，只能选 ≤k−2 个连续段中的点。
根据贪心，选最大的那 k−2 个连通块即可。
k=1
对于 k=1，相当于让最大值最小，这个东西看上去很二分。
首先观察性质：分成的段长度只会是 ⌈nm⌉ 或 ⌈nm⌉−1，如果出现 ≤⌈nm⌉−1 的显然将长度为 ⌈nm⌉ 分给他一个更优。
然后显然我们只会选择 nmod 个长度为 \lceil \frac{n}{m} \rceil 的段。
由于我们二分的答案是最大值，所以要求其他所有段都 \leq ans。
既然要比大小，先把所有长度为 \lceil \frac{n}{m} \rceil 的段拎出来排序（具体可以用 后缀数组）。
然后又是一个贪心。如果能放 \lceil \frac{n}{m} \rceil 肯定尽量先放；否则就放一个 \lceil \frac{n}{m} \rceil - 1。
因为如果能放但是没有放肯定是不优的，毕竟不知道后面还有没有机会放。
后缀数组里面 swap 得改成直接赋值才能过。
原来我写了十一次错误的后缀数组。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int T, n, m, k;
char s[N];
int Len[N];
void sub1() {
for (int ans = 9; ans >= 0; ans--) {
if (ans == 0) return puts("1"), void();
int l = 1, r = 0, sum = 0, tot = 0;
while (r + 1 <= n) {
l = r + 1, r = l;
if ((s[l] ^ 48) > ans) continue;
while (r < n && (s[r + 1] ^ 48) <= ans) r++;
if (l == 1 || r == n) sum += r - l + 1;
else Len[++tot] = r - l + 1;
}
sort(Len + 1, Len + 1 + tot), reverse(Len + 1, Len + 1 + tot);
for (int i = 1; i <= min(k - 2, tot); i++) sum += Len[i];
if (sum < m - k + 1) return printf("%d\n", ans + 1), void();
}
}
int sa[N], rk[N], cnt[N];
int x[N << 1], y[N << 1];
void init_SA() {
int v = 9;
for (int i = 0; i <= v; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) ++cnt[ x[i] = (int)(s[i] ^ '0') ];
for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;
for (int len = 1; ; len <<= 1) {
int tot = 0;
for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > len) y[++tot] = sa[i] - len;
for (int i = 0; i <= v; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) ++cnt[ x[i] ];
for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;
tot = 0;
for (int i = 0; i <= n + 5; i++) y[i] = x[i], x[i] = 0;
for (int i = 1; i <= n; i++) {
if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
else x[sa[i]] = ++tot;
}
v = tot;
if (v == n) break;
}
for (int i = 1; i <= n; i++) rk[sa[i]] = i;
}
int id[N], len;
inline bool cmp(int a, int b) { return rk[a] < rk[b]; } //按排名排序下标
bool check(int x) { //选择的排名不能 > x
int now = 1, cnt = n % m; //需要填 cnt 个长度为 len
while (now <= n) {
if (now + len - 1 <= n && cnt > 0 && rk[now] <= x) now += len, cnt--;
else now += len - 1;
if (!cnt) return 1;
}
return (!cnt);
}
void clr() { for (int i = 0; i <= n + 1; i++) id[i] = sa[i] = rk[i] = x[i] = y[i] = 0; }
void solve() {
scanf("\n %d%d%d\n %s", &n, &m, &k, s + 1);
if (k > 1) return sub1(), void();
init_SA(), len = (n - 1) / m + 1;
if (len == 1) {
char mx = '0';
for (int i = 1; i <= n; i++) mx = max(mx, s[i]);
putchar(mx), putchar('\n');
return;
}
if (n % m == 0) {
for (int i = 1; i <= m; i++) id[i] = (i - 1) * len + 1;
sort(id + 1, id + 1 + m, cmp);
int pos = id[m];
for (int i = pos; i <= pos + len - 1; i++) putchar(s[i]); putchar('\n');
return;
}
for (int i = 1; i <= n - len + 1; i++) id[i] = i; //挑选出所有长度至少为 len 的后缀
sort(id + 1, id + 1 + (n - len + 1), cmp);
int l = 1, r = n - len + 1;
while (l < r) {
int mid = l + r >> 1;
if (check(rk[id[mid]])) r = mid;
else l = mid + 1;
}
int pos = id[l];
for (int i = pos; i <= pos + len - 1; i++) putchar(s[i]); putchar('\n');
}
int main() {
scanf("%d", &T);
while (T--) solve(), clr();
return 0;
}
