問題文

あなたは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 が成立する。

入力例 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 番目の部分点の制約を満たします。