CF1530G.What a Reversal

You have two strings $a$ and $b$ of equal length $n$ consisting of characters 0 and 1, and an integer $k$.

You need to make strings $a$ and $b$ equal.

In one step, you can choose any substring of $a$ containing exactly $k$ characters 1 (and arbitrary number of characters 0) and reverse it. Formally, if $a = a_1 a_2 \ldots a_n$, you can choose any integers $l$ and $r$ ($1 \le l \le r \le n$) such that there are exactly $k$ ones among characters $a_l, a_{l+1}, \ldots, a_r$, and set $a$ to $a_1 a_2 \ldots a_{l-1} a_r a_{r-1} \ldots a_l a_{r+1} a_{r+2} \ldots a_n$.

Find a way to make $a$ equal to $b$ using at most $4n$ reversals of the above kind, or determine that such a way doesn't exist. The number of reversals doesn't have to be minimized.

你有两个长度均为 $n$ 的字符串 $a$ 和 $b$，它们仅由字符 0 和 1 组成，以及一个整数 $k$。

你需要使字符串 $a$ 和 $b$ 相等。

在每一步操作中，你可以选择 $a$ 的任意一个子串，该子串恰好包含 $k$ 个字符 1（可含任意数量的字符 0），并将其反转。形式化地说，若 $a = a_1 a_2 \ldots a_n$，则你可以任选整数 $l$ 和 $r$（满足 $1 \le l \le r \le n$），使得在字符 $a_l, a_{l+1}, \ldots, a_r$ 中恰好有 $k$ 个 1，然后将 $a$ 替换为

$$a_1 a_2 \ldots a_{l-1}\; a_r a_{r-1} \ldots a_l\; a_{r+1} a_{r+2} \ldots a_n.$$

请找出一种方法，在至多 $4n$ 次上述类型的反转操作内使 $a$ 变为 $b$；若不存在这样的方法，则判定其不可能。反转次数无需最小化。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). Description of the test cases follows.

Each test case consists of three lines. The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2000$; $0 \le k \le n$).

The second line contains string $a$ of length $n$.

The third line contains string $b$ of the same length. Both strings consist of characters 0 and 1.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 2000$）。随后是各测试用例的描述。

每个测试用例由三行组成。每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2000$；$0 \le k \le n$）。

第二行包含一个长度为 $n$ 的字符串 $a$。

第三行包含一个等长的字符串 $b$。两个字符串均由字符 0 和 1 组成。

保证所有测试用例中 $n$ 的总和不超过 $2000$。

For each test case, if it's impossible to make $a$ equal to $b$ in at most $4n$ reversals, print a single integer $-1$.

Otherwise, print an integer $m$ ($0 \le m \le 4n$), denoting the number of reversals in your sequence of steps, followed by $m$ pairs of integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$), denoting the boundaries of the substrings of $a$ to be reversed, in chronological order. Each substring must contain exactly $k$ ones at the moment of reversal.

Note that $m$ doesn't have to be minimized. If there are multiple answers, print any.

对于每个测试用例，如果无法在至多 $4n$ 次翻转操作内使 $a$ 等于 $b$，则输出单个整数 $-1$。

否则，首先输出一个整数 $m$（$0 \le m \le 4n$），表示你所构造的操作序列中翻转操作的次数；随后输出 $m$ 对整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$），按时间顺序给出每次对字符串 $a$ 进行翻转操作的子串边界。每次翻转操作所作用的子串在执行翻转时必须恰好包含 $k$ 个 1。

注意：$m$ 不必是最小可能值。若存在多个合法答案，输出任意一个即可。

In the first test case, after the first reversal $a = $ 011010, after the second reversal $a = $ 010110, after the third reversal $a = $ 010101.

在第一个测试用例中，第一次翻转后 $a = $ 011010，第二次翻转后 $a = $ 010110，第三次翻转后 $a = $ 010101。