题目描述

高桥君有一个由小写英文字母组成、长度为 $N$ 的字符串 $S$。高桥君决定对 $S$ 进行 $K$ 次如下操作：

• 令 $T$ 为 $S$ 的反转字符串，将 $S$ 和 $T$ 按此顺序连接，得到字符串 $U$。
• 从 $U$ 中选择一个连续的、长度为 $N$ 的子串 $S'$，用 $S'$ 替换 $S$。

请你求出经过 $K$ 次操作后，所有可能作为最终 $S$ 的字符串中，字典序最小的那个。

输入格式

输入以如下格式从标准输入中给出。

$N$ $K$ $S$

输出格式

请输出经过 $K$ 次操作后，所有可能作为最终 $S$ 的字符串中，字典序最小的那个。

输入输出样例 #1

输入 #1

5 1
bacba

输出 #1

aabca

输入输出样例 #2

输入 #2

10 2
bbaabbbaab

输出 #2

aaaabbaabb

说明/提示

限制条件

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

样例解释 1

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