D. Копирование строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны две строки $$$s$$$ и $$$t$$$ длиной $$$n$$$, ваша цель — преобразовать $$$s$$$ в $$$t$$$ с помощью серии следующих операций:

  • Постройте новую строку $$$s'$$$ длиной $$$n$$$, где $$$s'_1=s_1$$$. Для каждого $$$1 \lt i \le n$$$, $$$s'_i$$$ может быть либо $$$s_i$$$, либо $$$s_{i-1}$$$. Затем замените $$$s$$$ на $$$s'$$$.

Ваша задача — достичь этого преобразования, используя минимальное количество операций. Вам также нужно вывести решение, выводя построенную строку $$$s'$$$ после каждой операции. Если преобразование невозможно выполнить за меньшее или равное количество операций, чем $$$k_{\mathrm{max}}$$$, выведите -1.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k_{\mathrm{max}}$$$ ($$$1 \le n \cdot k_{\mathrm{max}} \le 10^6$$$) — длина двух строк и максимальное количество операций, которые можно использовать.

Вторая строка каждого теста содержит одну строку $$$s$$$ длиной $$$n$$$.

Третья строка каждого теста содержит одну строку $$$t$$$ длиной $$$n$$$.

Гарантируется, что сумма $$$nk_{\mathrm{max}}$$$ по всем наборам входных данных не превышает $$$10^6$$$.

Гарантируется, что обе строки $$$s$$$ и $$$t$$$ состоят из строчных латинских букв.

Выходные данные

Для каждого набора входных данных:

  • Если вы не можете достичь преобразования за меньшее или равное количество операций, чем $$$k_{\mathrm{max}}$$$, просто выведите -1 в одной строке.
  • В противном случае, в первой строке выведите одно целое число $$$k \le k_{\mathrm{max}}$$$ — минимальное количество операций. Затем следуют $$$k$$$ строк, каждая из которых содержит одну строку длиной $$$n$$$ — строку после каждой операции.

Если существует несколько решений, выведите любое.

Пример
Входные данные
7
4 1
abcd
aabd
2 2
ab
ab
5 3
abcde
abbcc
9 1
egcnyeluw
eegccyelw
10 3
vzvylxxmsy
vvvvvllxxx
4 6
acba
aaac
5 7
acabb
aaaca
Выходные данные
1
aabd
0
2
abbcd
abbcc
-1
3
vvzvylxxms
vvvzvllxxm
vvvvvllxxx
2
aacb
aaac
2
aacab
aaaca
Примечание

В первом наборе входных данных, очевидно, $$$s$$$ можно преобразовать в $$$t$$$ за одну операцию.

Во втором наборе изначально $$$s=t$$$, поэтому операция не требуется.

В четвертом наборе, хотя $$$s$$$ можно преобразовать в $$$t$$$ за две операции, но $$$k_{\mathrm{max}}=1$$$, поэтому ответ — -1.