NAIPC 2019

#### Start

2019-03-02 18:00 UTC

## NAIPC 2019

#### End

2019-03-02 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -256 days 11:46:21

5:00:00

0:00:00

# Problem ICutting 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

dda