题目描述

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

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

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

输入格式

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

$N$ $K$ $S$

输出格式

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

题目大意

给定一个长度为 $n$ 的只包含小写字母的字符串 $s$ 和正整数 $k$ , 求进行 $k$ 次如下操作后:

将 $s$ 和 $s$ 的翻转拼接($s$ 在前)得到 $t$ , 从 $t$ 中截取长度为 $n$ 的子串作为新的 $s$.

字典序最小的 $s$ .

$n\leqslant 5000,k\leqslant 10^9$

5 1
bacba

aabca

10 2
bbaabbbaab

aaaabbaabb

提示

制約

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

Sample Explanation 1

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