配点 : $1300$ 点

問題文

高橋君は英小文字からなる長さ $N$ の文字列 $S$ を持っています。 高橋君は $S$ に対して以下の操作を $K$ 回行うことにしました。

• $S$ を反転した文字列を $T$ として、$S$ と $T$ をこの順に連結して得られる文字列を $U$ とする。
• ある $U$ の連続する長さ $N$ の部分文字列を $S'$ として、$S$ を $S'$ で置き換える。

最終的な $S$ として考えられる文字列の内、辞書順で最小のものを求めてください。

制約

• $1 \leq N \leq 5000$
• $1 \leq K \leq 10^9$
• $|S|=N$
• $S$ は英小文字からなる

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$S$

出力

最終的な $S$ として考えられる文字列の内、辞書順で最小のものを出力せよ。

5 1
bacba

aabca

$S=$bacbaのとき、$T=$abcab, $U=$bacbaabcabであるので $S'=$aabcaとするのが最適です。

10 2
bbaabbbaab

aaaabbaabb