A14323 | 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.

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$ .

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.