|Codeforces Round #330 (Div. 1)|
You are given a non-empty line s and an integer k. The following operation is performed with this line exactly once:
Your task is to determine the lexicographically smallest string that could be the result of applying the given operation to the string 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.
In the single line print the lexicographically minimum string s' which can be obtained as a result of performing the described operation.