D. Copy String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two strings $$$s$$$ and $$$t$$$ of length $$$n$$$, you aim to transform $$$s$$$ into $$$t$$$ through a series of the following operations:

  • Construct a new string $$$s'$$$ of length $$$n$$$,where $$$s'_1=s_1$$$. For each $$$1 \lt i \le n$$$, $$$s'_i$$$ can be either $$$s_i$$$ or $$$s_{i-1}$$$. Then replace $$$s$$$ with $$$s'$$$.

Your task is to achieve this transformation using the minimum number of operations. You also need to output the solution by printing the constructed string $$$s'$$$ after each operation. If the transformation cannot be achieved in less than or equal to $$$k_{\mathrm{max}}$$$ operations, output -1.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k_{\mathrm{max}}$$$ ($$$1 \le n \cdot k_{\mathrm{max}} \le 10^6$$$) — the length of two strings and the maximum number of operations that can be used.

The second line of each test case contains one string $$$s$$$ of length $$$n$$$.

The third line of each test case contains one string $$$t$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$nk_{\mathrm{max}}$$$ over all test cases does not exceed $$$10^6$$$.

It is guaranteed that both $$$s$$$ and $$$t$$$ consist of lowercase Latin letters.

Output

For each test case:

  • If you cannot achieve the transformation in less than or equal to $$$k_{\mathrm{max}}$$$ operations, simply output -1 in one line.
  • Otherwise, on the first line, output one integer $$$k \le k_{\mathrm{max}}$$$ — the minimum number of operations. Then $$$k$$$ lines follow, each line contains one string of length $$$n$$$ — the string after each operation.

If there are multiple solutions, output any.

Example
Input
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
Output
1
aabd
0
2
abbcd
abbcc
-1
3
vvzvylxxms
vvvzvllxxm
vvvvvllxxx
2
aacb
aaac
2
aacab
aaaca
Note

In the first test case, obviously $$$s$$$ can be transformed to $$$t$$$ in one operation.

In the second test case, initially $$$s=t$$$, so no operation is needed.

In the fourth test case, although $$$s$$$ can be transformed to $$$t$$$ in two operations, but $$$k_{\mathrm{max}}=1$$$, so the answer is -1.