D. Serval и сдвиг-сдвиг-сдвиг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Serval есть два $$$n$$$-битных двоичных числа $$$a$$$ и $$$b$$$. Он хочет поделиться этими числами с Toxel.

Так как Toxel больше нравится число $$$b$$$, Serval решил изменить $$$a$$$ на $$$b$$$ с помощью нескольких (возможно, нуля) операций. За одну операцию Serval может выбрать любое положительное целое число $$$k$$$ от $$$1$$$ до $$$n$$$, и заменить $$$a$$$ на одно из следующих чисел:

  • $$$a\oplus(a\ll k)$$$
  • $$$a\oplus(a\gg k)$$$

Другими словами, операция сдвигает каждый бит числа $$$a$$$ налево или направо на $$$k$$$ позиций, при этом переполненные биты удаляются, а недостающие биты дополняются $$$0$$$. Побитовое исключающее ИЛИ результата сдвига и изначального $$$a$$$ присваиваются обратно $$$a$$$.

У Serval нет много времени. Он хочет применить не более $$$n$$$ операций, чтобы изменить $$$a$$$ на $$$b$$$. Пожалуйста, помогите ему найти последовательность операций, или определите, что невозможно изменить $$$a$$$ на $$$b$$$ за не более $$$n$$$ операций. Вам не нужно минимизировать количество операций.

В этой задаче $$$x\oplus y$$$ обозначает побитовое исключающее ИЛИ чисел $$$x$$$ и $$$y$$$. $$$a\ll k$$$ и $$$a\gg k$$$ обозначают логический сдвиг влево и логический сдвиг вправо.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1\le t\le2\cdot10^{3}$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1\le n\le2\cdot10^{3}$$$) — количество битов в числах $$$a$$$ и $$$b$$$.

Вторая и третья строка каждого набора входных данных содержат бинарную строку длины $$$n$$$, обозначающую $$$a$$$ и $$$b$$$, соответственно. Строки содержат только символы 0 и 1.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^{3}$$$.

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

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

Иначе, в первой строке выведите количество операций $$$m$$$ ($$$0\le m\le n$$$).

Если $$$m>0$$$, во второй строке выведите $$$m$$$ целых чисел $$$k_{1},k_{2},\dots,k_{m}$$$ обозначающих операции. Если $$$1\le k_{i}\le n$$$, это обозначает логический сдвиг влево $$$a$$$ на $$$k_{i}$$$ позиций. Если $$$-n\le k_{i}\le-1$$$, это обозначает логический сдвиг вправо $$$a$$$ на $$$-k_{i}$$$ позиций.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
5
00111
11000
1
1
1
3
001
000
Выходные данные
2
3 -2
0
-1
Примечание

В первом наборе входных данных:

Первая операция изменяет $$$a$$$ на $$$\require{cancel}00111\oplus\cancel{001}11\underline{000}=11111$$$.

Вторая операция изменяет $$$a$$$ на $$$\require{cancel}11111\oplus\underline{00}111\cancel{11}=11000$$$.

Биты с зачеркиванием — это биты с переполнением, которые удаляются. Биты с подчеркиванием являются дополненными битами.

Во втором наборе входных данных $$$a$$$ уже равно $$$b$$$, поэтому никаких операций делать не нужно.

В третьем наборе входных данных можно показать, что $$$a$$$ невозможно изменить на $$$b$$$.