← 返回题目列表

Codeforces · 594/E

E. 切割线

中文机器翻译题面 查看原题

给定一个非空行 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