Cutting the Line

2000ms

262144K

Description:

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₁ + t₂ + ... + 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'₁t'₂... 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.

Input:

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.

Output:

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

Sample Input:

aba
2

Sample Output:

aab

Sample Input:

aaaabacaba
2

Sample Output:

aaaaabacab

Sample Input:

bababa
1

Sample Output:

ababab

Sample Input:

abacabadabacaba
4

Sample Output:

aababacabacabad

Informação

Provedor Codeforces

Código CF594E