AT_discovery_2016_qual_c アメージングな文字列は、きみが作る！

你正在参加 DISCO 公司的面试，面试官给你布置了一项挑战：提供一个仅由小写字母组成的字符串 $S$，并要求你通过以下三种操作中的某一种，恰好进行 $K$ 次，改造该字符串，并生成一个在你的理解中“令人惊叹”的新字符串。 可选择的操作有： 1. 删除字符串 $S$ 中的第 $i$ 个字符（1 ≤ i ≤ |S|）。 2. 将字符串 $S$ 中的第 $i$ 个字符替换为另一小写字母（1 ≤ i ≤ |S|）。 3. 在字符串 $S$ 的第 $i$ 个位置插入一个小写字母（1 ≤ i ≤ |S|+1）。 你的目标是通过 $K$ 次操作，生成出字典序最小的字符串，以惊艳面试官。 对于字符串 $X$，$|X|$ 表示字符串 $X$ 的长度。 对于两个字符串 $s = s_1s_2s_3\ldots s_n$ 和 $t = t_1t_2t_3\ldots t_m$，如果满足下列任一条件，则 $s$ 在字典序上小于 $t$： - 对于某个整数 $i$（1 ≤ i ≤ min(n, m)），满足对于任何 $j$（1 ≤ j < i），有 $s_j = t_j$ 且 $s_i < t_i$。 - 对于任意整数 $i$（1 ≤ i ≤ min(n, m)），有 $s_i = t_i$ 且 $n < m$。

输入包括两行： - 第一行为给定的字符串 $S$，只包含小写字母，满足 2 ≤ |S| ≤ 300,000。 - 第二行为整数 $K$，表示必须进行的操作次数，满足 1 ≤ K ≤ |S| - 1。

输出通过对 $S$ 进行 $K$ 次操作后生成的字典序最小的字符串，注意输出末尾应包含换行。

### 部分分数 本题设置了不同数据范围的部分分数。 - 如果满足条件 2 ≤ |S| ≤ 10，1 ≤ K ≤ min(|S|-1, 4)，则解答正确可得 10 分。 - 如果满足条件 2 ≤ |S| ≤ 200，则额外得 10 分。 - 如果满足条件 2 ≤ |S| ≤ 1,000，则额外得 20 分。 - 如果满足条件 2 ≤ |S| ≤ 300,000，则额外得 60 分，总共能得到 100 分。 ### 示例解释 1 通过在 $S$ 开头插入一个字母 `a`，可以得到字符串 `aabc`，这是进行一次操作后可以获得的字典序最小的字符串。这一示例满足第一个部分分数的要求。 ### 示例解释 2 通过删除 $S$ 的第 2 个和第 3 个字符，可以得到字符串 `a`，这是进行两次操作后可以获得的字典序最小的字符串。这一示例满足第一个部分分数的要求。 ### 示例解释 3 通过替换 $S$ 的第 2 个字符，可以得到字符串 `aab`，这是进行一次操作后可以获得的字典序最小的字符串。这一示例满足第一个部分分数的要求。 **本翻译由 AI 自动生成**