
Во время своей работы алгоритм сжатия данных методом "сортировки блока" применяет к блокам данных
преобразование, которое определяется следующим образом.
Строка P называется ротацией строки S, если она образована циклическим
сдвигом символов S, т.е.
если S=a1a2…aN, где aiiый символ
строки S, то P=apap+1…aNa1…
ap-1, где 1£p£N. Рассмотрим таблицу M размера
N´N,
строками которой есть все ротации строки S,
отсортированные в лексикографическом (словарном) порядке по возрастанию.
Пусть строка L есть последний столбик таблицы M. Прямое преобразование получает
на вход строку S, выдает строку L и число K номер строки таблицы M,
который содержит строку S. (Если таких строк несколько, выдается номер любой из них).
Для S="abraka" таблица M изображена на рисунке. Строка S находится во второй
строке таблицы M, L="karaab".
Задача
Напишите программу ABRAKA, которая выполняет обратное преобразование, т.е. получает на вход строку L
и число K, и выдает строку S.
Входные данные
Первая строка входного файла ABRAKA.DAT содержит два целых числа:
K и N, 1£N£30000, 1£K£N. Вторая строка
содержит N символов строки L маленьких латинских букв.
Пример входных данных
Выходные данные
Единственная строка выходного файла ABRAKA.SOL должна содержать строку S.
Пример выходных данных