A2. Префиксные перевороты (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Различия между версиями заключаются в ограничениях на $$$n$$$ и необходимое количество операций. Вы можете делать взломы только если обе версии задачи сданы.

Есть две бинарные строки $$$a$$$ и $$$b$$$ длины $$$n$$$ (бинарная строка это строка, состоящая из символов $$$0$$$ и $$$1$$$). За одну операцию вы выбираете префикс строки $$$a$$$, меняете все биты этого префикса на другие ($$$0$$$ меняется на $$$1$$$, $$$1$$$ меняется на $$$0$$$) и переворачиваете этот префикс. За одну операцию вы выполняете оба этих действия.

Например, если $$$a=001011$$$ и вы выбираете префикс длины $$$3$$$, строка становится равной $$$011011$$$. Затем, если вы вы выберете всю строку как префикс для операции, она станет равной $$$001001$$$.

Ваша задача превратить строку $$$a$$$ в строку $$$b$$$ за не больше, чем $$$2n$$$ операций. Можно доказать, что это всегда возможно.

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

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

В первой строке каждого набора входных данных находится единственное целое число $$$n$$$ ($$$1\le n\le 10^5$$$)  — длина бинарных строк.

Следующие две строки содержат две бинарные строки $$$a$$$ и $$$b$$$ длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите целое число $$$k$$$ ($$$0\le k\le 2n$$$), затем $$$k$$$ целых чисел $$$p_1,\ldots,p_k$$$ ($$$1\le p_i\le n$$$). Здесь $$$k$$$ равно количеству операций, которое вы использовали и $$$p_i$$$ равно длине префикса в $$$i$$$-й операции.

Пример
Входные данные
5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1
Выходные данные
3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1
Примечание

В первом наборе входных данных процесс превращения выглядит так: $$$01\to 11\to 00\to 10$$$.

Во втором наборе входных данных процесс превращения выглядит так: $$$01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$$$.

В третьем наборе входных данных данные строки уже совпадают. Другим решением будет, например, сделать операцию с префиксом длины $$$2$$$, от чего строка $$$a$$$ не поменяется.