Даны две строки $$$s$$$ и $$$t$$$ длиной $$$n$$$, ваша цель — преобразовать $$$s$$$ в $$$t$$$ с помощью серии следующих операций:
Ваша задача — достичь этого преобразования, используя минимальное количество операций. Вам также нужно вывести решение, выводя построенную строку $$$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$$$ состоят из строчных латинских букв.
Для каждого набора входных данных:
Если существует несколько решений, выведите любое.
74 1abcdaabd2 2abab5 3abcdeabbcc9 1egcnyeluweegccyelw10 3vzvylxxmsyvvvvvllxxx4 6acbaaaac5 7acabbaaaca
1aabd02abbcdabbcc-13vvzvylxxmsvvvzvllxxmvvvvvllxxx2aacbaaac2aacabaaaca
В первом наборе входных данных, очевидно, $$$s$$$ можно преобразовать в $$$t$$$ за одну операцию.
Во втором наборе изначально $$$s=t$$$, поэтому операция не требуется.
В четвертом наборе, хотя $$$s$$$ можно преобразовать в $$$t$$$ за две операции, но $$$k_{\mathrm{max}}=1$$$, поэтому ответ — -1.
