17003번 - 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.

Each input will begin with a line with a single integer c (1 ≤ c ≤ 2·10⁵), 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 ≤ k ≤ |s| ≤ 10⁵, s ∈ [a−z]^*), separated by a space.

The total length of all strings in the input will be at most 10⁶.

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