D. Copy Stringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputGiven 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 < 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.InputEach 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.OutputFor 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.ExampleInput74 1abcdaabd2 2abab5 3abcdeabbcc9 1egcnyeluweegccyelw10 3vzvylxxmsyvvvvvllxxx4 6acbaaaac5 7acabbaaacaOutput1aabd02abbcdabbcc-13vvzvylxxmsvvvzvllxxmvvvvvllxxx2aacbaaac2aacabaaacaNoteIn 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.