题目描述

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

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

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

输入格式

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

$N$ $K$ $S$

输出格式

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

样例 1

输入

5 1
bacba

输出

aabca

样例 2

输入

10 2
bbaabbbaab

输出

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}$ 是最优的。

由 ChatGPT 4.1 翻译