問題文

あなたはDISCO社の面接を受けています。 あなたは面接官から「英小文字だけからなる文字列 $S$ を与えるので、ある $3$ 種類の操作から $1$ つ選んで行うということをちょうど $K$ 回だけ行ってあなたが考えるアメージングな文字列を作ってください」というお題を与えられました。

許されている操作は以下の $3$ つです。

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))$ に関して、 $1≦j<i$ を満たす任意の整数 $j$ において $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$ 回操作を行って作ることが可能な文字列のうち辞書順最小のものを $1$ 行に出力せよ。末尾の改行を忘れないこと。

部分点

この問題には部分点が設定されている。

• $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$ 回の操作で作ることが可能な辞書順最小の文字列です。
• このケースは、 $1$ 番目の部分点の制約を満たします。

入力例 2

abc
2

出力例 2

a

• $S$ の $2$ 文字目と $3$ 文字目を削除した文字列aが $2$ 回の操作で作ることが可能な辞書順最小の文字列です。
• このケースは、 $1$ 番目の部分点の制約を満たします。

入力例 3

acb
1

出力例 3

aab

• $S$ の $2$ 文字目を置換した文字列aabが $1$ 回の操作で作ることが可能な辞書順最小の文字列です。
• このケースは、 $1$ 番目の部分点の制約を満たします。