Problem Description

Do you know how strings are compared lexicographically? If not, you might find the definition in Problem B of ABC007 helpful.

This time, we want you to solve a problem where lexicographical order plays a crucial role.

First, you are given a string $ S $ of length $ N $ consisting only of lowercase English letters (a-z). You need to rearrange the characters of $ S $ to form a string $ T = T_1, T_2, ..., T_N $ that is the smallest possible in lexicographical order.

However, there is one restriction on how you can rearrange the characters. You are also given an integer $ K $, and you must ensure that the number of characters that change their position from $ S $ to $ T $ is at most $ K $. In other words, the number of indices $ i $ (where $1 \leq i \leq N$) such that $S_i \neq T_i$ must be at most $ K $.

Note: This problem is more difficult than the usual C problem in ABC. You can click the button below to read an explanation of the idea to solve this problem as a hint. Take your time to work on it.

Show Hint
The key point is that when aiming for the smallest lexicographical order, it is better to have smaller alphabets at the beginning of the string. So, first, consider making the first character of $ T $ as small as possible.

Start by trying to place the smallest alphabets from $ S $ at the beginning of $ T $ until you find one that works. Then, proceed to the second character, the third character, and so on (a more detailed explanation is provided in Sample Input/Output 2).

What you need to check is whether you can start $ T $ with a certain string $ t $. This can be determined by cleverly rearranging the unused characters from $ S $ to minimize the number of mismatches with the latter part of $ S $ and ensuring the total number of mismatches is within $ K $.

For example, if $ S = $program and $ K = 3 $, and you want to check if the first 3 characters of $ T $ can be aro. In this case, there is already one mismatch with the first 3 characters of $ S pro, so you need to keep the remaining mismatches to 2 or less. That is, you need to rearrange the unused characters pgrm to minimize mismatches with gram.

Try to figure out how to implement this method and the specific part of the check on your own.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ S $

• The first line contains an integer $ N $ ($1 \leq N \leq 100$) representing the length of the string, and an integer $ K $ ($0 \leq K \leq N$) representing the maximum number of characters that can change position.
• The second line contains a string $ S $ of $ N $ lowercase English letters.

Output Format

Output the string that can be formed by rearranging the characters of $ S $ with at most $ K $ characters changing their original position, which is the smallest in lexicographical order.

Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 2
abc

Sample Output #1

abc

Sample Input #2

7 2
atcoder

Sample Output #2

actoder

Sample Input #3

7 7
atcoder

Sample Output #3

acdeort

Sample Input #4

10 3
helloworld

Sample Output #4

dehloworll

Notes/Hints

Sample Explanation 1

Since the number of characters that can change position is at most $ 2 $, you do not need to rearrange any characters. In this case, not rearranging any characters results in the smallest string.

Sample Explanation 2

• First, consider if the first character of $ T $ can be a (the smallest alphabet in the original string atcoder).
• Since the first character of $ S $ is already a, you can make the first character of $ T $ a.
• Next, consider if the second character can be c.
• If the first two characters of $ T $ are ac, at least c has changed its position.
• So, you need to consider if you can rearrange the remaining alphabets deort to minimize mismatches with coder.
• This time, rearranging deort to toder results in $ T = $actoder with 2 position changes.
• Hence, the second character is determined to be c.
• Next, consider if the third character can be d.
• If the first three characters of $ T $ are acd, both c and d have changed their positions.
• So, you cannot move any more characters from their original positions in the remaining part.
• However, no matter how you rearrange the remaining alphabets eort, you cannot match them exactly with oder.
• So, the third character cannot be d.
• Since d does not work, consider if the third character can be e.
• ...
• ...
  By proceeding this way, you can eventually reach the answer actoder.

Sample Explanation 3

Since $ K = 7 $, you can rearrange the characters freely. As mentioned in the problem statement, in this case, you can arrange the characters alphabetically to form the smallest string.

见题面 Input 部分

见题面 Output 部分