[AGC037E] Reversing and Concatenating

给定一个长度为 $n$ 的只包含小写字母的字符串 $s$ 和正整数 $k$ , 求进行 $k$ 次如下操作后: 将 $s$ 和 $s$ 的翻转拼接($s$ 在前)得到 $t$ , 从 $t$ 中截取长度为 $n$ 的子串作为新的 $s$. 字典序最小的 $s$ . $n\leqslant 5000,k\leqslant 10^9$

[problemUrl]: https://atcoder.jp/contests/agc037/tasks/agc037_e 高橋君は英小文字からなる長さ $ N $ の文字列 $ S $ を持っています。 高橋君は $ S $ に対して以下の操作を $ K $ 回行うことにしました。 - $ S $ を反転した文字列を $ T $ として、$ S $ と $ T $ をこの順に連結して得られる文字列を $ U $ とする。 - ある $ U $ の連続する長さ $ N $ の部分文字列を $ S' $ として、$ S $ を $ S' $ で置き換える。 最終的な $ S $ として考えられる文字列の内、辞書順で最小のものを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ S $

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

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`とするのが最適です。