问题文

你知道按字典顺序比较字符串的方法吗？如果不知道，建议阅读 ABC007 的 B 问题，其中介绍了这个定义。

这次，我希望你解决一个涉及到字典顺序的重要问题。

首先，给定一个仅包含 $N$ 个英文小写字母（a-z）的字符串 $S$。请找出所有可以通过重新排列 $S = S_1,\\,S_2,\\,...,\\,S_N$ 中的字符而形成的字符串 $T = T_1,\\,T_2,\\,...,\\,T_N$ 中的字典顺序最小的字符串。

然而，有一个限制条件：只能进行一次字符位置变换，即给定一个整数 $K$，必须保证变换后的字符串中不同的字符数量不超过 $K$。也就是说，只能进行那些字符不匹配（$S_i ≠ T_i$）的位置不超过 $K$ 个的排列方式。

※该问题相比平时的 ABC C 问题更加困难。点击下面的按钮，可以阅读关于解决这个问题的思路的提示。请耐心思考。

显示提示

重要的一点是，当追求字典顺序最小时，最好将较小的字母放在字符串的开头。因此，首先考虑如何使 $T$ 的第一个字符尽可能小。

我们需要判断是否可以用某个字符串 $t$ 作为开头来构建 $T$。判断的方法是：找出字符串 $S$ 中未使用的字符，将它们与字符串后面的部分进行重新排列，使得与它们不匹配的字符数量尽量少，并且整体而言不匹配的数量不超过 $K$。

例如，假设 $S =$ program，$K = 3$，我们想要判断是否可以将 $T$ 的前三个字符变为 aro。此时，我们已经知道 aro 和 $S$ 的前三个字符 pro 有 1 个不匹配，所以我们必须通过合理地排列剩下的未使用字符 pgrm 来减少与 gram 不匹配的数量，直到不匹配的数量不超过 2。

至于具体如何编写程序来实现这一方法和判断部分，我们尽量自己努力吧。

输入

输入从标准输入中按以下格式提供。

$N$ $K$ $S$

• 第 1 行包含两个整数 $N$ ($1 ≦ N ≦ 100$) 和 $K$ ($0 ≦ K ≦ N$)，分别表示字符串的长度和可以变换的字符数的上限。
• 第 2 行包含 $N$ 个由英文小写字母组成的字符串 $S$。

输出

输出一个字符串，该字符串是通过重新排列 $S$ 的字符构成的，并且所得到的字符串的位置变换不超过 $K$ 个的字符数量，在字典顺序上最小的字符串。注意输出末尾要包含换行符。

输入例子1

3 2
abc

输出例子1

abc

位置变换的字符数量必须不超过 2，所以即使不对字符串进行重新排列也是可以的。

在这个示例中，不进行任何重新排列是最小的情况。

输入例子2

7 2
atcoder

输出例子2

actoder

• 首先考虑将 $T$ 的第一个字符设置为 a（原始字符串 atcoder 中最小的字母）是否可行。
  • 由于最初的 $S$ 的第一个字符已经是 a，我们可以将 $T$ 的第一个字符设为 a。（例如，如果不进行任何重新排序，即 $S = T$，则可以确认将 $T$ 的第一个字符设为 a 是可行的）
  • 所以 $T$ 的第一个字符确定为 a。
• 接下来，考虑将第二个字符设为 c 是否可行。
  • 假设 $T$ 的前两个字符是 ac，那么在此时至少有一个字符 c 与原始位置不同。
  • 所以，对于剩下的部分 coder，我们需要考虑合理地排列未使用的字母 deort 来尽量减少与 gram 不匹配的数量，并且将整体的不匹配数量保持在 1 以下。
  • 在这