P16103 [ICPC 2019 NAIPC] Cutting Strings

给定一个字符串 $s$ 和一个整数 $k$。你可以从 $s$ 中删除至多 $k$ 个互不相交的子串。你的任务是找到字典序（即字母顺序）最大的结果字符串。 例如，对于字符串 **abcdcada** 和 $k=2$，你可以选择子串 [**abc**]d[**ca**]da 并删除它们，得到 **dda**。

每个输入的第一行包含一个整数 $c$（$1 \leq c \leq 2\cdot10^5$），表示你需要解决的测试用例个数。 接下来的 $c$ 行，每行包含一个整数 $k$ 和一个字符串 $s$（$1 \leq k \leq |s| \leq 10^5$，$s$ 由小写字母组成），两者之间用空格分隔。 输入中所有字符串的总长度不超过 $10^6$。

对于每个测试用例，输出通过从 $s$ 中删除至多 $k$ 个互不相交的子串所能得到的字典序最大的字符串。

翻译由 DeepSeek V3.2 完成