G. Вот это переворот
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть две строки $$$a$$$ и $$$b$$$ равной длины $$$n$$$, состоящие из символов 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$$$ единиц, и сделать $$$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$$$.

Найдите способ сделать строки $$$a$$$ и $$$b$$$ равными, используя не более $$$4n$$$ переворотов такого рода, или определите, что такого способа не существует. Минимизировать число переворотов не нужно.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Каждый набор входных данных состоит из трёх строк. Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2000$$$; $$$0 \le k \le n$$$).

Вторая строка содержит строку $$$a$$$ длины $$$n$$$.

Третья строка содержит строку $$$b$$$ той же длины. Обе строки состоят из символов 0 и 1.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

Выходные данные

Для каждого набора входных данных, если невозможно сделать $$$a$$$ и $$$b$$$ равными, используя не более $$$4n$$$ переворотов, выведите одно целое число $$$-1$$$.

В противном случае выведите целое число $$$m$$$ ($$$0 \le m \le 4n$$$) — число переворотов в вашей последовательности шагов, и $$$m$$$ пар целых чисел $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — границы подстрок $$$a$$$, которые нужно перевернуть, в хронологическом порядке. Каждая подстрока должна содержать ровно $$$k$$$ единиц на момент переворота.

Обратите внимание, что $$$m$$$ минимизировать не нужно. Если существует несколько решений, выведите любое из них.

Пример
Входные данные
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
Выходные данные
3
1 2
3 4
5 6
1
1 6
-1
-1
-1
5
4 8
8 9
3 6
1 4
3 6
Примечание

В первом наборе входных данных после первого переворота $$$a = $$$ 011010, после второго переворота $$$a = $$$ 010110, после третьего переворота $$$a = $$$ 010101.