QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 1024 MB

# 3009. Cutting Strings

统计

Problem Description

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 $\texttt{abcdcada}$ and $k=2$, you can choose the substrings $\texttt{[abc]d[ca]da}$ and remove them to get $\texttt{dda}$.

Input

Each input will begin with a line with a single integer $c$($1 \leq c \leq 2 \times 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 \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

Output the largest string, alphabetically, that you can get by removing $k$ or fewer non-intersecting substrings from $s$.

Sample

Sample Input

4
2 abcdcada
1 ababb
2 ababb
1 dadbdcdbdad

Sample Output

dda
bb
bbb
ddcdbdad