Абракадабра
Во время своей работы алгоритм сжатия данных методом "сортировки блока" применяет к блокам данных преобразование, которое определяется следующим образом.
Строка P называется ротацией строки S, если она образована циклическим сдвигом символов S, то есть если S=a[1]a[2]…a[N], где a[i] — i–ый символ строки S, то P = a[p]a[p+1]…a[N]a[1]…a[p-1], где 1 ≤ p ≤ N. Рассмотрим таблицу M размером N×N, строками которой являются все ротации строки S, отсортированные в лексикографическом (словарном) порядке по возрастанию.
Пусть строка L явялется последним столбиком таблицы M. Прямое преобразование получает на вход строку S, видаёт строку L и число K — номер строки таблицы M, содержащий строку S. (Если таких строк несколько, выдаётся номер любой из них).
Для S = 'abraka' таблицу M изображено на рисунке. Строка S находится во второй строке таблицы M, L = 'karaab'.
Напишите программу, которая выполняет обратное преобразование, то есть получает на вход строку L и число K, и выводит строку S.
Входные данные
Первая строка входного файла содержит два целыих числа: K и N, 1 ≤ N ≤ 30000, 1 ≤ K ≤ N. Вторая строка содержит N символов строки L — маленькие латинские буквы.
Выходные данные
Единственная строка выходного файла должна содержать строку S.