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

[problemUrl]: https://atcoder.jp/contests/discovery2016-qual/tasks/discovery_2016_qual_c あなたは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\

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 点が得られる。 ### Sample Explanation 1 \- $ S $ の先頭に`a`を挿入した文字列`aabc`が $ 1 $ 回の操作で作ることが可能な辞書順最小の文字列です。 - このケースは、 $ 1 $ 番目の部分点の制約を満たします。 ### Sample Explanation 2 \- $ S $ の $ 2 $ 文字目と $ 3 $ 文字目を削除した文字列`a`が $ 2 $ 回の操作で作ることが可能な辞書順最小の文字列です。 - このケースは、 $ 1 $ 番目の部分点の制約を満たします。 ### Sample Explanation 3 \- $ S $ の $ 2 $ 文字目を置換した文字列`aab`が $ 1 $ 回の操作で作ることが可能な辞書順最小の文字列です。 - このケースは、 $ 1 $ 番目の部分点の制約を満たします。