What a Reversal
Contest: Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))
Difficulty rating: 3300
Tags: constructive algorithms

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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

Example input:
6
6 1
101010
010101
6 3
101010
010101
6 0
101010
010101
6 6
101010
010101
4 2
0000
1111
9 2
011100101
101001011

Example output:
3
1 2
3 4
5 6
1
1 6
-1
-1
-1
5
4 8
8 9
3 6
1 4
3 6

Editorial:
First of all, the number of 1's in $$$a$$$ and $$$b$$$ must match. Let $$$c$$$ be the number of 1's in $$$a$$$.
If $$$k = 0$$$ or $$$k > c$$$, we can not do a meaningful reversal, so we just check if $$$a = b$$$.
If $$$k = c$$$, we can not change the contents of $$$a$$$ between the leftmost and the rightmost 1's, we can only reverse it and shift with regard to the outside 0's. It's easy to check whether $$$a$$$ can become equal to $$$b$$$ then, and at most $$$2$$$ steps are required if so.
Otherwise, suppose $$$0 < k < c$$$. Since our operations are reversible, we'll apply a usual trick: we'll transform both strings into some canonical representations in at most $$$2n$$$ steps each. If $$$a$$$'s and $$$b$$$'s canonical representations don't match, we'll prove that there is no solution. Otherwise, we can transform $$$a$$$ into $$$b$$$ in at most $$$4n$$$ steps: transform $$$a$$$ into the canonical representation, and then perform the steps transforming $$$b$$$ into the canonical representation, but in reverse order. What representation is canonical is for us to determine later.
We'll focus on one string now. Let's write down the lengths of blocks of consecutive 0's in the string. Formally, let $$$p_0, p_1, p_2, \ldots, p_c$$$ be the sequence consisting of the number of 0's: before the first 1, between the first and the second 1's, $$$\ldots$$$, after the last 1. Note that some $$$p_i$$$ might be equal to $$$0$$$.
What does a single reversal do to the sequence of blocks? $$$k+1$$$ consecutive blocks get reversed, and additionally, the 0's in the leftmost and the rightmost block of these $$$k+1$$$ blocks can be redistributed arbitrarily.
It turns out that we don't need more than $$$k+2$$$ blocks to achieve our goal (we'll see that later), so let's start with the following. Let $$$p_i$$$ be the rightmost block such that $$$p_i > 0$$$. If $$$i \le k+1$$$, stop. Otherwise, perform two reversals of blocks $$$p_{i-k}, p_{i-k+1}, \ldots, p_i$$$, moving all the 0's from $$$p_i$$$ to $$$p_{i-k}$$$ in the process, effectively making $$$p_i$$$ zero, and repeat. After this process, only $$$p_0, p_1, \ldots, p_{k+1}$$$ can still be non-zero.
Now, consider what happens if we reverse $$$p_0, p_1, \ldots, p_k$$$, and then reverse $$$p_1, p_2, \ldots, p_{k+1}$$$ without changing any values: sequence $$$p_0, p_1, \ldots, p_{k+1}$$$ will change to $$$p_k, p_{k+1}, p_0, p_1, \ldots, p_{k-1}$$$, that is, will cyclically shift by two positions to the right.
Suppose we repeat this pair of reversals $$$k+1$$$ times. The $$$k$$$-th ($$$0$$$-indexed) position initially contains $$$p_k$$$, after the first pair it will contain $$$p_{k-2}$$$, then $$$p_{k-4}$$$ and so on. Assume that $$$k$$$ is odd. Then every block will reach the $$$k$$$-th position at some point!
Now, during the first reversal in the pair, let's move all 0's from the $$$k$$$-th block to the $$$0$$$-th block, and keep the second reversal in the pair as is, without changing the values. Then, after $$$k+1$$$ pairs of reversals, all the 0's will move to the $$$0$$$-th block, that is, all $$$p_1, p_2, \ldots, p_{k+1}$$$ will become zero.
We can for sure call this representation — with all of $$$p_1, p_2, \ldots, p_c$$$ zeroed out, and $$$p_0$$$ equal to the number of 0's in the original string — canonical. It follows that if the number of 1's in $$$a$$$ and $$$b$$$ is equal to $$$c$$$, $$$k < c$$$ and $$$k$$$ is odd, a solution always exists.
Let's move on to the case when $$$k$$$ is even. In this case, since a pair of reversals makes a cyclic shift by $$$2$$$, only even-numbered blocks will appear at the $$$k$$$-th position. However, notice that this is not a coincidence: when $$$k$$$ is even, whatever reversal we perform, even-numbered blocks only interact with even-numbered blocks, and odd-numbered blocks interact with odd-numbered blocks. In particular, the sum of $$$p_0, p_2, p_4, \ldots$$$ can never change, and the sum of $$$p_1, p_3, p_5, \ldots$$$ can never change either.
Thus, when $$$k$$$ is even, let's call the following representation canonical: $$$p_0$$$ contains the sum of all initial values of $$$p_0, p_2, p_4, \ldots$$$; $$$p_{k+1}$$$ contains the sum of all initial values of $$$p_1, p_3, p_5, \ldots$$$; and all the other $$$p_i$$$'s are zeros.
We can reach this representation in a similar way to the odd $$$k$$$ case, using pairs of reversals.
Note that similar to the $$$k$$$-th position which contains blocks $$$p_k, p_{k-2}, p_{k-4}, \ldots$$$ during the process, the $$$1$$$-st position contains blocks $$$p_1, p_{k+1}, p_{k-1}, p_{k-3}, \ldots$$$ during the process.
During the first reversal in each pair, as in the previous case, we'll move all the 0's from the $$$k$$$-th block to the $$$0$$$-th block. During the second reversal in each pair, we'll move all the 0's from the $$$1$$$-st block to the $$$k+1$$$-th block. After $$$k+1$$$ pairs of reversals (actually just $$$\frac{k}{2}$$$ pairs are enough), we'll zero out all the values except for $$$p_0$$$ and $$$p_{k+1}$$$.
All in all, we have found a way to reach the canonical representation in $$$2c \le 2n$$$ steps, as desired.