Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. What a Reversal

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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

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

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.

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

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

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 13:04:19 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|