题目描述

Takahashi 有一个长度为 $N$ 的字符串 $S$，由小写英文字母组成。他将对这个字符串执行以下操作 $K$ 次：

• 令 $T$ 为将 $S$ 反转得到的字符串，$U$ 为按照 $S$ 和 $T$ 的顺序连接得到的字符串。
• 令 $S'$ 为 $U$ 的某个连续子串，长度为 $N$，将 $S$ 替换为 $S'$。

在所有经过 $K$ 次操作后可能得到的字符串 $S$ 中，找出字典序最小的字符串。

约束条件

• $1 \leq N \leq 5000$
• $1 \leq K \leq 10^9$
• $|S|=N$
• $S$ 由小写英文字母组成。

输入

输入通过标准输入给出，格式如下：

$N$ $K$ $S$

输出

打印出可能的字符串 $S$ 中字典序最小的字符串。

示例输入 1

5 1
bacba

示例输出 1

aabca

当 $S=$bacba 时，$T=$abcab，$U=$bacbaabcab，$S'$ 的最优选择是 $S'=$aabca。

示例输入 2

10 2
bbaabbbaab

示例输出 2

aaaabbaabb