Добро пожаловать в очередную задачу про взлом кодового замка! Исследователи Уитфилд и Мартин наткнулись на необычный сейф, внутри которого, по слухам, находятся несметные богатства, среди которых можно найти решение задачи дискретного логарифма!
На сейфе, разумеется, установлен кодовый замок, на экране которого в каждый момент времени показывается строка, состоящая из 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 операций.
Выходные данные
Если нельзя получить t из s, используя не более 6100 операций «shift», выведите единственное число - 1.
Иначе в первой строке выведите количество операций k (0 ≤ k ≤ 6100). В следующей строке выведите k чисел xi, соответствующих операциям «shift xi» (0 ≤ xi ≤ n), в том порядке, в котором их нужно применить.