问题描述

你正在参加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$...$s_n$ 和 $t=t_1t_2t_3$...$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$ $K$

• 第 $1$ 行为由面试官给出的只由小写英文字母组成的字符串 $S (2≦|S|≦300,000)$。
• 第 $2$ 行为表示需要进行的操作次数的整数 $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

abc
1

输出样例 1

aabc

• 在字符串 $S$ 的开头插入字符 a，制作出的字符串 aabc 是通过 $1$ 次操作可以制作的字典顺序最小的字符串。
• 这个样例满足第一部分得分条件。

输入样例 2

abc
2

输出样例 2

a

• 删除字符串 $S$ 的第二个字符和第三个字符，制作出的字符串 a 是通过 $2$ 次操作可以制作的字典顺序最小的字符串。
• 这个样例满足第一部分得分条件。

输入样例 3

acb
1

输出样例 3

aab

• 用字符 a 替换字符串 $S$ 的第二个字符，制作出的字符串 aab 是通过 $1$ 次操作可以制作的字典顺序最小的字符串。
• 这个样例满足第一部分得分条件。