#P13013. [AGC037E] Reversing and Concatenating

    ID: 12197 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300字符串贪心枚举动态规划杜教筛树哈希半平面交

[AGC037E] Reversing and Concatenating

题目描述

高桥君有一个由小写英文字母组成、长度为 NN 的字符串 SS。高桥君决定对 SS 进行 KK 次如下操作:

  • 令 TT 为 SS 的反转字符串,将 SS 和 TT 按此顺序连接,得到字符串 UU。
  • 从 UU 中选择一个连续的、长度为 NN 的子串 S′S',用 S′S' 替换 SS。

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

输入格式

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

NN KK SS

输出格式

请输出经过 KK 次操作后,所有可能作为最终 SS 的字符串中,字典序最小的那个。

输入输出样例 #1

输入 #1

5 1
bacba

输出 #1

aabca

输入输出样例 #2

输入 #2

10 2
bbaabbbaab

输出 #2

aaaabbaabb

说明/提示

限制条件

  • 1≤N≤50001 \leq N \leq 5000
  • 1≤K≤1091 \leq K \leq 10^9
  • ∣S∣=N|S| = N
  • SS 仅由小写英文字母组成

样例解释 1

当 S=bacbaS = \texttt{bacba} 时,T=abcabT = \texttt{abcab},U=bacbaabcabU = \texttt{bacbaabcab},此时选择 S′=aabcaS' = \texttt{aabca} 是最优的。