题目描述

给定两个长度为 $n$ 的字符串 $s$ 和 $t$，你希望通过一系列操作将 $s$ 转换为 $t$。

操作定义如下：

1. 构造一个新的字符串 $s'$，长度为 $n$，满足 $s'_1 = s_1$。
2. 对于每个 $1 < i \le n$，可以选择 $s'_i = s_i$ 或 $s'*i = s*{i-1}$。
3. 然后将 $s$ 替换为 $s'$。

你的任务是在 尽可能少的操作次数 内完成转换。 你还需要输出每次操作后构造的字符串 $s'$。

如果无法在不超过 $k_{\text{max}}$ 次操作内完成转换，输出 -1。

输入格式

输入包含多组测试数据。

第一行输入一个整数 $t$：

$1 \le t \le 10^4$

接下来每组测试包含：

• 第一行包含两个整数 $n, k_{\text{max}}$：

$1 \le n \cdot k_{\text{max}} \le 10^6$

• 第二行包含一个长度为 $n$ 的字符串 $s$。
• 第三行包含一个长度为 $n$ 的字符串 $t$。

保证：

• 所有测试中 $\sum n \cdot k_{\text{max}} \le 10^6$
• 字符串 $s$ 和 $t$ 仅包含小写字母。

输出格式

对于每组测试：

• 如果无法在不超过 $k_{\text{max}}$ 次操作内完成转换，输出一行 -1。
• 否则，第一行输出一个整数 $k \le k_{\text{max}}$，表示最少操作次数。 接下来的 $k$ 行，每行输出一个长度为 $n$ 的字符串，表示每次操作后得到的 $s'$。

若存在多种合法解，可输出任意一种。

样例

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

样例解释

• 样例 1： 显然 $s$ 可以通过一次操作变为 $t$。

• 样例 2： 初始 $s = t$，无需操作。

• 样例 4： 虽然可以在两次操作内将 $s$ 转换为 $t$，但是 $k_{\text{max}} = 1$，所以输出 -1。