CF594E.Cutting the Line

You are given a non-empty line s and an integer k. The following operation is performed with this line exactly once:

• A line is split into at most k non-empty substrings, i.e. string s is represented as a concatenation of a set of strings s = _t_1 + _t_2 + ... + t__m, 1 ≤ m ≤ k.
• Some of strings t__i are replaced by strings t__i__r, that is, their record from right to left.
• The lines are concatenated back in the same order, we get string s' = t'1_t_'2... t'm, where t'i equals t__i or t__i__r.

Your task is to determine the lexicographically smallest string that could be the result of applying the given operation to the string s.

给你一个非空字符串 $s$ 和一个整数 $k$。对这个字符串恰好执行一次如下操作：

• 将字符串分割为至多 $k$ 个非空子串，即字符串 $s$ 表示为若干字符串的连接：$s = t_1 + t_2 + \dots + t_m$，其中 $1 \le m \le k$。
• 将其中某些子串 $t_i$ 替换为其反转（即从右向左书写）后的字符串 $t_i^r$。
• 将这些（可能已被替换的）子串按原顺序重新连接，得到字符串 $s' = t'_1 t'_2 \dots t'_m$，其中每个 $t'_i$ 要么等于 $t_i$，要么等于 $t_i^r$。

你的任务是确定：对字符串 $s$ 执行上述操作后，所能得到的字典序最小的字符串。

The first line of the input contains string s (1 ≤ |s| ≤ 5 000 000), consisting of lowercase English letters. The second line contains integer k (1 ≤ k ≤ |s|) — the maximum number of parts in the partition.

输入的第一行包含字符串 $s$（$1 \leq |s| \leq 5\,000\,000$），由小写英文字母组成。第二行包含整数 $k$（$1 \leq k \leq |s|$）—— 分割部分数的最大值。

In the single line print the lexicographically minimum string s' which can be obtained as a result of performing the described operation.

在单行中输出执行上述操作后所能得到的字典序最小的字符串 $s'$。