Abracadabra
During its operation, the data compression algorithm using the "block sorting" method applies a transformation to data blocks, defined as follows.
A string P is called a rotation of a string S if it is formed by a cyclic shift of the characters of S. Specifically, if S = a[1]a[2]…a[N], where a[i] is the i-th character of the string S, then P = a[p]a[p+1]…a[N]a[1]…a[p-1], where 1 ≤ p ≤ N. Consider a table M of size N×N, whose rows are all rotations of the string S, sorted in lexicographical (dictionary) order in ascending order.
Let the string L be the last column of the table M. The direct transformation takes the string S as input and outputs the string L along with the number K — the row number of the table M that contains the string S. (If there are multiple such rows, the number of any one of them is output).
For S = 'abraka', the table M is shown in the figure. The string S is located in the second row of the table M, and L = 'karaab'.
Write a program that performs the inverse transformation, i.e., takes the string L and the number K as input, and outputs the string S.
Input
The first line of the input file contains two integers: K and N, where 1 ≤ N ≤ 30000 and 1 ≤ K ≤ N. The second line contains N characters of the string L — lowercase Latin letters.
Output
The single line of the output file should contain the string S.