training_2004_12_04 - Восстановление строки

Задача C. Восстановление строки ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	СПб 2005	Ограничение времени:	2 сек
Входной файл:	restore.in	Ограничение памяти:	64 Мб
Выходной файл:	restore.out

Условие

В одном алгоритме сжатия используется преобразование строк, суть которого состоит в следующем. Рассмотрим некоторую строку. Возьмем все ее возможные циклические сдвиги и расположим их в словарном порядке в виде квадратной таблицы. В получившейся таблице выделим последний столбец, который, если его записать в виде строки, и будет являться результатом описанного преобразования.

Рассмотрим, что происходит при таком преобразовании со строкой «abraca»:

abraca

→

abraca
bracaa
racaab
acaabr
caabra
aabrac

→

1: aabrac
2: abraca
3: acaabr
4: bracaa
5: caabra
6: racaab

→

caraab

Итак, в результате мы получили строку «caraab». В дополнение к найденной строке мы определяем также позицию исходной строки в отсортированном списке циклических сдвигов (в данном случае 2). Оказывается, что исходя из этих двух данных, первоначальная строка восстанавливается однозначно. Напишите программу, которая сделает это.

Формат входного файла

В первой строке входного файла записано целое число k — номер исходной строки в отсортированном списке циклических сдвигов. На следующей строке записан результат преобразования. Входные данные таковы, что исходная строка всегда существует. Сама строка состоит из символов с кодами от 33 до 255.

Формат выходного файла

В выходной файл выведите исходную строку.

Ограничения

Длина заданной строки не превосходит 10⁵.

Примеры тестов

№	Входной файл (`restore.in`)	Выходной файл (`restore.out`)
1	`2 caraab`	`abraca`
2	`34 eehnyollwwhvnewoeoriretdtdaaneanogb`	`whenwehavetolearntodowelearnbydoing`
3	`5 bbccaabbaaaaaa`	`abacabaabacaba`