Добро пожаловать в очередную задачу про взлом кодового замка! Исследователи Уитфилд и Мартин наткнулись на необычный сейф, внутри которого, по слухам, находятся несметные богатства, среди которых можно найти решение задачи дискретного логарифма!

На сейфе, разумеется, установлен кодовый замок, на экране которого в каждый момент времени показывается строка, состоящая из n маленьких букв английского алфавита. Изначально на экране показывается строка s. Уитфилд и Мартин выяснили, что сейф откроется, когда на экране окажется строка t.

Строку на экране можно изменять с помощью операции «shift x». Для того, чтобы применить эту операцию, исследователи выбирают число x от 0 до n включительно. После этого текущая строка p = αβ изменяется на строку β^Rα, где длина β равна x, а длина α равна n - x. Иными словами, суффикс строки p длины x разворачивается и переставляется в начало строки. Например, применение операции «shift 4» заменит строку «abcacb» на строку «bcacab», поскольку α = ab, β = cacb, β^R = bcac.

Исследователи боятся, что если применить слишком много операций «shift», то замок заблокируется навсегда. Они просят вас найти способ получить на экране строку t, используя не более чем 6100 операций.