Спецслужбы обнаружили действующего иностранного агента. Шпиона то есть. Установили наблюдение и выяснили, что каждую неделю он через Интернет посылает кому-то странные нечитаемые тексты. Чтобы выяснить, к какой информации получил доступ шпион, требуется расшифровать информацию. Сотрудники спецслужб проникли в квартиру разведчика, изучили шифрующее устройство и выяснили принцип его работы.

На вход устройства подается строка текста 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, то таблица имеет такой вид:

1. aabracadabr = S₁₁
2. abraabracad = S₈
3. abracadabra = S₁
4. acadabraabr = S₄
5. adabraabrac = S₆
6. braabracada = S₉
7. bracadabraa = S₂
8. cadabraabra = S₅
9. dabraabraca = S₇
10. raabracadab = S₁₀
11. racadabraab = S₃

И результатом работы устройства является число 3 и строка rdarcaaaabb.

Это все, что известно про шифрующее устройство. А вот дешифрующего устройства не нашли. Но поскольку заведомо известно, что декодировать информацию можно (а иначе зачем же ее передавать?), Вам предложили помочь в борьбе с хищениями секретов и придумать алгоритм для дешифровки сообщений. А заодно и реализовать дешифратор.

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

ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz

Символы здесь выписаны в порядке возрастания.

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