task_7_1322

Задача 7 (1322. Шпион)

Условие

Спецслужбы обнаружили действующего иностранного агента. Шпиона то есть. Установили наблюдение и выяснили, что каждую неделю он через Интернет посылает кому-то странные нечитаемые тексты. Чтобы выяснить, к какой информации получил доступ шпион, требуется расшифровать информацию. Сотрудники спецслужб проникли в квартиру разведчика, изучили шифрующее устройство и выяснили принцип его работы.S₁ = s₁s₂...s_N. Получив ее, устройство строит все циклические перестановки этой строки, то есть S₂ = s₂s₃...s_Ns₁, ..., S_N = s_Ns₁s₂...s_N-1. Затем множество строк S₁, S₂, ..., S_N сортируется лексикографически по возрастанию. И в этом порядке строчки выписываются в столбец, одна под другой. Получается таблица размером N × N. В какой-то строке K этой таблицы находится исходное слово. Номер этой строки вместе с последним столбцом устройство и выдает на выход. Например, если исходное слово S₁ = abracadabra, то таблица имеет такой вид:
aabracadabr = S₁₁
abraabracad = S₈
abracadabra = S₁
acadabraabr = S₄
adabraabrac = S₆
braabracada = S₉
bracadabraa = S₂
cadabraabra = S₅
dabraabraca = S₇
raabracadab = S₁₀
racadabraab = S₃
И результатом работы устройства является число 3 и строка rdarcaaaabb. Это все, что известно про шифрующее устройство. А вот дешифрующего устройства не нашли. Но поскольку заведомо известно, что декодировать информацию можно (а иначе зачем же ее передавать?), Вам предложили помочь в борьбе с хищениями секретов и придумать алгоритм для дешифровки сообщений. А заодно и реализовать дешифратор.

Исходные данные

В первой и второй строках находятся соответственно целое число и строка, возвращаемые шифратором. Длина строки и число не превосходят 100000. Строка содержит лишь следующие символы: a-z, A-Z, символ подчеркивания. Других символов в строке нет. Лексикографический порядок на множестве слов задается таким порядком символов: ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz Символы здесь выписаны в порядке возрастания.

Результат

Выведите декодированное сообщение в единственной строке.

Примеры

Исходные данные	Результат
3 rdarcaaaabb	abracadabra