题目描述

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.

输入格式

Each input will begin with a line with a single integer $c$ ($1 \leq c \leq 2\cdot10^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 \leq k \leq |s| \leq 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 the largest string, alphabetically, that you can get by removing $k$ or fewer non-intersecting substrings from $s$.

4
2 abcdcada
1 ababb
2 ababb
1 dadbdcdbdad

dda
bb
bbb
ddcdbdad