Cutting Strings

문자열 s에서 겹치지 않는 부분 문자열을 최대 k개 제거해 남은 문자열이 사전순으로 가장 크도록 만들고, 그 결과를 출력한다.

어려움8문자열그리디동적 계획법스택아직 제출이 없습니다시간 제한10초메모리 제한512 MB

문제 설명

예제1

문제

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·105), 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| ≤ 105, s ∈ [a−z]*), separated by a space.

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

출력

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