Грю необходимо взломать сейф Вектора, в котором находятся чертежи ракеты, специально разработанной для миссии по похищению Луны. Разумеется, это не очень простая задача, поэтому поручать ее Миньонам не стоит. Поэтому решить ее предстоит вам.
Кодовый замок имеет экран, и на этом экране сейчас написана строка $$$s$$$, состоящая из маленьких букв английского алфавита. Любимое слово Вектора — строка $$$t$$$ той же длины, что и строка $$$s$$$. Грю уверен, что замок откроется, когда на экране вместо $$$s$$$ будет отображаться строка $$$t$$$.
Рядом с экраном есть поле для ввода целого числа и одна единственная кнопка. Доктор Нефарио проанализировал это устройство и сообщил Грю и вам, что в поле можно ввести любое целое число от $$$1$$$ до $$$|s|$$$, а при нажатии кнопки
Иными словами, суффикс строки $$$s$$$ длины $$$x$$$ разворачивается и переставляется в начало строки. Например, ввод числа $$$2$$$ и нажатие на кнопку заменит строку «arkshs» на «sharks».
Логично, что слишком большое количество нажатий на кнопку вызовет определенные подозрения, и увеличит ваши шансы быть пойманными, поэтому количество применений описанной операции ограничено. Найдите способ получить на экране строку $$$t$$$, используя не более чем $$$m$$$ операций.
Первая строка ввода содержит два целых числа $$$n$$$ и $$$m$$$ — длины строк $$$s$$$ и $$$t$$$, а также максимальное число операций ($$$1 \le n \le 2000$$$; $$$5100 \le m \le 10^4$$$).
Во второй и третьей строках ввода даны $$$s$$$ и $$$t$$$, состоящие из $$$n$$$ маленьких букв английского алфавита (символы от 'a' до 'z').
Если нельзя получить $$$t$$$ из $$$s$$$, используя не более $$$m$$$ нажатий на кнопку, выведите единственное число «-1». Иначе в первой строке выведите количество нажатий на кнопку $$$k$$$ ($$$0 \le k \le m$$$), а в следующей строке выведите через пробел $$$k$$$ целых чисел, $$$i$$$-е из которых равно числу, которое должно быть введено перед $$$i$$$-м нажатием кнопки.
Обратите внимание, что минимизировать количество нажатий на кнопку не требуется — достаточно просто уложиться в определенные ограничения.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
0 | – | примеры из условия | полная | |
1 | 9 | $$$n \le 8$$$, $$$m = 10^4$$$ | 0 | полная |
2 | 21 | $$$n \le 100$$$, $$$m = 10^4$$$ | 0, 1 | первая ошибка |
3 | 24 | $$$n \le 1000$$$, $$$m = 10^4$$$ | 0 – 2 | первая ошибка |
4 | 12 | $$$m = 10^4$$$ | 0 – 3 | первая ошибка |
5 | 12 | $$$m \ge 8100$$$ | 0 – 4 | первая ошибка |
6 | 11 | $$$m \ge 6100$$$ | 0 – 5 | первая ошибка |
7 | 11 | без дополнительных ограничений | 0 – 6 | первая ошибка |
6 10000
xyxzyy
yxyzyx
4
6 3 2 3
4 10000
xyzy
xyyx
-1
s
В первом примере после применения операций строка на экране будет изменяться следующим образом: