AT_abc009_3.[ABC009C] 辞書式順序ふたたび

你知道字符串的字典序比较吗？如果不知道，可以阅读 ABC007 的 B 问题 中的定义。

这次，你需要解决一个与字典序有关的问题。

首先，给定一个仅由小写英文字母（a-z）组成的长度为 $N$ 的字符串 $S$。请你在将 $S = S_1, S_2, ..., S_N$ 的字符重新排列后，构造出一个字符串 $T = T_1, T_2, ..., T_N$，使得 $T$ 在所有可以通过重新排列 $S$ 得到的字符串中，字典序最小。

不过，排列方式有一个限制。给定一个整数 $K$，要求原本位置发生变化的字符个数不能超过 $K$。也就是说，满足 $S_i \neq T_i$ 的 $i$（$1 \leq i \leq N$）的个数不能超过 $K$。

注意：本题比通常的 ABC C 题更难。你可以点击下方按钮查看解题思路提示，建议你认真思考后再查看。

::::info[显示提示]

在追求字典序最小时，让字符串的前面尽可能出现较小的字母是有利的。因此，首先考虑能否将 $T$ 的第一个字符设为尽可能小的字母。

依次尝试将 $S$ 中较小的字母放在 $T$ 的开头，找到第一个可行的字母后，将其作为 $T$ 的第一个字符。接着，在剩下的字符中，依次尝试将较小的字母放在 $T$ 的第二个字符位置，第三个、第四个字符同理确定（在样例 2 的解释中有更具体的说明）。

在尝试时，需要判断“能否让 $T$ 以某个字符串 $t$ 开头”。具体来说，就是判断能否用 $S$ 中还未使用的字符，通过合理排列，使得与 $S$ 后面部分的字符不一致的个数尽量少，并且总的不一致个数不超过 $K$。

例如，$S = $`program`，$K = 3$，现在想判断 $T$ 的前 $3$ 个字符能否为 aro。此时，aro 与 $S$ 的前 $3$ 个字符 pro 有 $1$ 个不一致，因此剩下部分的不一致个数必须不超过 $2$。也就是说，需要将还未用过的字符 pgrm 重新排列，使得与 $S$ 的后半部分 gram 的不一致个数尽量少，并且不超过 $2$，如果可以做到，则可行。

具体实现该方法以及判定部分的编程细节，请自行思考。

::::

输入按以下格式从标准输入读入。

$N$ $K$
$S$

• 第 $1$ 行包含两个整数 $N$（字符串长度，$1 \leq N \leq 100$）和 $K$（允许改变位置的字符数上限，$0 \leq K \leq N$）。
• 第 $2$ 行包含一个仅由小写英文字母组成的长度为 $N$ 的字符串 $S$。

请输出通过重新排列 $S$ 得到的、且原本位置发生变化的字符个数不超过 $K$ 的所有字符串中，字典序最小的字符串 $T$。输出后需换行。

样例解释 1

由于允许改变位置的字符数最多为 $2$，所以完全不进行排列也是可以的。在本例中，不进行任何排列得到的字符串就是字典序最小的。

样例解释 2

• 首先，考虑能否将 $T$ 的第一个字符设为 a（原字符串 atcoder 中最小的字母）。
• 这次 $S$ 的第一个字符本身就是 a，因此可以将 $T$ 的第一个字符设为 a。（例如完全不排列，$S = T$，此时 $T$ 的第一个字符就是 a）
• 因此，$T$ 的第 $1$ 个字符确定为 a。
• 接着，考虑能否将第 $2$ 个字符设为 c。
• 若 $T$ 的前两个字符为 ac，此时至少 c 的位置发生了变化。
• 因此，需要判断能否用还未使用的字母 deort 重新排列，使得与 $S$ 的第 $3$ 个字符及之后的 coder 匹配时，位置变化的字符数不超过 $1$。
• 这次可以将 deort 排列为 toder，得到 $T = $actoder，此时位置变化的字符数为 $2$。
• 因此，第 $2$ 个字符确定为 c。
• 接着，考虑能否将第 $3$ 个字符设为 d。
• 若 $T$ 的前 $3$ 个字符为 acd，此时 c 和 d 的位置都发生了变化。
• 因此，$T$ 的第 $4$ 个及之后的字符不能再有位置变化。
• 但无论如何排列剩下的 eort，都无法与 $S$ 的 oder 完全一致。
• 因此，第 $3$ 个字符不能为 d。
• 依次尝试 e、o 等，最终可以确定答案为 actoder。

样例解释 3

由于 $K = 7$，可以任意排列。此时，将所有字母按字母顺序排列即可得到字典序最小的字符串。

由 ChatGPT 4.1 翻译