Задача 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.

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

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

Ограничения

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

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

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

0.104s 0.020s 15