给定一个非空行 s 和一个整数 k。以下操作仅对该行执行一次:
- 一行最多被分成 k 个非空子字符串,即字符串 s 表示为一组字符串 s = t1 + t2 + ... + tm, 1 ≤ m ≤ k 的串联。
- 一些字符串 ti 被替换为字符串 tir,即它们从右到左的记录。
- 这些行以相同的顺序连接回去,我们得到字符串 s' = t'1t'2... t'm,其中 t'i 等于 ti 或 tir。
您的任务是确定按字典顺序排列的最小字符串,该字符串可能是将给定操作应用于字符串 s 的结果。
输入
输入的第一行包含字符串 s (1 ≤ |s| ≤ 5 000 000),由小写英文字母组成。第二行包含整数 k (1 ≤ k ≤ |s|) — 分区中的最大部分数。
输出
在单行中打印字典顺序最小的字符串 s',该字符串可以作为执行所描述的操作的结果而获得。
示例
输入 #1
aba 2
输出 #1
aab
输入 #2
aaaabacaba 2
输出 #2
aaaaabacab
输入 #3
bababa 1
输出 #3
ababab
输入#4
abacabadabacaba 4
输出#4
aababacabacabad