Problem I
Cutting Strings
You are given a string $s$ and an integer $k$. You can remove at most $k$ non-intersecting substrings from $s$. Your task is to find the alphabetically (i.e., dictionary order) largest resulting string.
For example, with string abcdcada and $k{=}2$, you can choose the substrings [abc]d[ca]da and remove them to get dda.
Input
Each input will begin with a line with a single integer $c$ ($1\! \le \! c\! \le \! 2{\cdot }10^5$), which is the number of cases you must solve.
Each of the next $c$ lines will contain an integer $k$ and a string $s$ ($1\! \le \! k\! \le \! |s|\! \le \! 10^5, s\! \in \! [a{-}z]^*$), separated by a space.
The total length of all strings in the input will be at most $10^6$.
Output
Output the largest string, alphabetically, that you can get by removing $k$ or fewer non-intersecting substrings from $s$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 abcdcada 1 ababb 2 ababb 1 dadbdcdbdad |
dda bb bbb ddcdbdad |
