题目内容

给定一个长度为 $n$ 的字符串 $S$（仅由小写英文字母组成）以及一个整数 $k$（$0 \le k < n$）。你可以从 $S$ 的开头删去 $l$ 个字符，并从末尾删去 $k-l$ 个字符，其中 $l$ 是满足 $0 \le l \le k$ 的整数。操作后得到一个长度为 $m = n - k$ 的连续子串。在所有可能的删法中，请找出字典序最小的子串。

字符串的字典序比较规则：从左到右依次比较对应位置的字符。若在某位置出现不同字符，则字符较小的字符串字典序更小；若一直比较到某一字符串结束仍未出现不同，则较短的字符串字典序更小。

你需要处理多组测试数据。保证所有测试数据的 $n$ 总和不超过 $4 \times 10^6$，单个 $n$ 不超过 $10^5$，数据组数 $T$ 不超过 $10^5$，且 $0 \le k < n$。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。接下来每组数据包含两行：第一行输入两个整数 $n$ 和 $k$；第二行输入一个长度为 $n$ 且仅由小写字母组成的字符串 $S$。所有数据均满足题目中的约束条件。

输出描述

对于每组测试数据，输出一行，包含一个长度为 $m = n - k$ 的字符串，表示字典序最小的删后子串。

样例1

输入

2
6 3
abcabc
4 1
zaba

输出

abc
aba

说明

第一组数据：字符串长度为 6，删除 k=3 个字符后保留长度 m=3。允许的起点位置 $l$ 取 $0,1,2,3$，对应的长度为 3 的子串分别为 abc、bca、cab、abc。其中字典序最小的是 abc。

第二组数据：$n=4,k=1$，保留长度 $3$。起点 $l=0$ 得到 zab，起点 $l=1$ 得到 aba。aba 的字典序严格小于 zab，因此输出 aba。

样例2

输入

3
5 2
cbcba
4 2
abba
5 0
hello

输出

bcb
ab
hello

说明

第一组数据：$n=5,k=2$，字符串 cbcba，保留长度 $3$。可选起点 $l=0,1,2$，对应子串为 cbc、bcb、cba。比较首字符即可看出 bcb 最小，故答案为 bcb。

第二组数据：$n=4,k=2$，字符串 abba，保留长度 $2$。$l=0,1,2$ 对应的子串为 ab、bb、ba，其中 ab 的字典序最小。

第三组数据是边界情况 $k=0$，无法从两端删除任何字符，保留长度为 $5$，答案就是原字符串 hello。