Взлом сейфа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Грю необходимо взломать сейф Вектора, в котором находятся чертежи ракеты, специально разработанной для миссии по похищению Луны. Разумеется, это не очень простая задача, поэтому поручать ее Миньонам не стоит. Поэтому решить ее предстоит вам.

Кодовый замок имеет экран, и на этом экране сейчас написана строка $$$s$$$, состоящая из маленьких букв английского алфавита. Любимое слово Вектора — строка $$$t$$$ той же длины, что и строка $$$s$$$. Грю уверен, что замок откроется, когда на экране вместо $$$s$$$ будет отображаться строка $$$t$$$.

Рядом с экраном есть поле для ввода целого числа и одна единственная кнопка. Доктор Нефарио проанализировал это устройство и сообщил Грю и вам, что в поле можно ввести любое целое число от $$$1$$$ до $$$|s|$$$, а при нажатии кнопки

  1. строка $$$s$$$ разбивается на префикс $$$p$$$ длины $$$|s| - x$$$ (строку из первых $$$|s| - x$$$ символов $$$s$$$) и суффикс $$$q$$$ длины $$$x$$$ (строку из оставшихся $$$x$$$ символов), где $$$x$$$ — введенное в поле число;
  2. и затем $$$s$$$ заменяется на $$$\overline{q^{\mathtt{rev}}p}$$$, то есть на конкатенацию (запись подряд) развернутой строки $$$q$$$ и строки $$$p$$$.

Иными словами, суффикс строки $$$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примеры из условияполная
19$$$n \le 8$$$, $$$m = 10^4$$$0полная
221$$$n \le 100$$$, $$$m = 10^4$$$0, 1первая ошибка
324$$$n \le 1000$$$, $$$m = 10^4$$$0 – 2первая ошибка
412$$$m = 10^4$$$0 – 3первая ошибка
512$$$m \ge 8100$$$0 – 4первая ошибка
611$$$m \ge 6100$$$0 – 5первая ошибка
711без дополнительных ограничений0 – 6первая ошибка

Примеры

Входные данные
6 10000
xyxzyy
yxyzyx
Выходные данные
4
6 3 2 3
Входные данные
4 10000
xyzy
xyyx
Выходные данные
-1

Примечание

s

В первом примере после применения операций строка на экране будет изменяться следующим образом:

  1. xyxzyy $$$\rightarrow$$$ yyzxyx
  2. yyzxyx $$$\rightarrow$$$ xyxyyz
  3. xyxyyz $$$\rightarrow$$$ zyxyxy
  4. zyxyxy $$$\rightarrow$$$ yxyzyx