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 .

输入描述:

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.