kevin-doesnt-like-his-string

Link to Russian translation of the problem.

Kevin has a string S of length N, but he doesn't like it. In order to create a string which he likes more, he can cut K characters out of this string and insert these characters in the same places from which they were cut out (possibly in a different order).

Let's have string abacbca and cut characters at positions 2, 4 and 5. We will get the string a_a__ca and characters 'b' , 'c' and 'b'. One of the possible ways to insert them is acabbca.

Kevin wants to obtain the lexicographically smallest string this way. Help him.

Note: A string S is lexicographically smaller than another string T if there's such an index i that S[i] < T[i] and for all j < i, S[j] = T[j].

Input format:

The first line of the input will contain two space-separated integers N and K. The second line will contain the string S. All characters of S are lowercase English letters.

Output format:

Print the lexicographically smallest string which Kevin can obtain using the described process.

Constraints
1 ≤ K ≤ N ≤ 10^5
N ≤ 20 in test data 15% of all points
N ≤ 5000 in test data worth 50% of all points
K = 2 in test data worth 20% of all points

SAMPLE INPUT
7 3
acbdaxa

SAMPLE OUTPUT
aabcaxd

Explanation

Kevin can cut out the letters at positions 2, 4 and 7.

Source: hackerearth | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Greedy algorithms


Solutions: