题目描述

In the north tower of Tianqiu Valley's ruins, there are some flame torch puzzles and Lumine the traveler is facing the last and the hardest one.

There are $n$ torches in a circle and some torches have been ignited initially. The $i$-th and the $(i \bmod n +1)$-th are adjacent for all $1 \le i \le n$.

To solve the puzzle, all the torches should be ignited. In each move, Lumine can ignite an extinguished torch, and the status of the adjacent torches will be reversed affected by the supernatural. That is, each of the adjacent torches will be ignited if it is currently extinguished, or be extinguished if it is currently ignited.

Time is money, Lumine wants to solve the puzzle in $2n$ moves or determine that the puzzle is unsolvable.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line of the input contains an integer $n$ ($3 \le n \le 10^5$) indicating the number of torches in the circle.

The second line contains a binary string $s_1s_2\cdots s_n$ of length $n$ ($s_i \in \{\text{`0'}, \text{`1'}\}$). If $s_i = \text{`0'}$ the $i$-th torch is extinguished initially; If $s_i = \text{`1'}$ the $i$-th torch is ignited initially. It is guaranteed that not all the torches have been ignited initially.

It is also guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

输出格式

If the puzzle is unsolvable, output 0.

Otherwise, output an integer $k$ $(1 \le k \le 2n)$ in the first line indicating the number of moves Lumine needs to solve the puzzle. Then output a line containing $k$ integers $t_1, t_2, \cdots, t_k$ separated by a space, where $t_i$ indicating that Lumine will ignite the $t_i$-th torch in the $i$-th move. If there are multiple answers print any of them.

Please, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!

题目大意

有 $n$ 个火炬排成一个环，编号为 $1,2,3,...,n$，输入一个长度为 $n$ 的二进制字符串 $s$，表示这 $n$ 个火炬是否已经被点燃（初始状态）。

你可以点燃一个熄灭的火炬 $s_i$，但两侧火炬的状态也会随之逆转（即 $s_{{i-1}}$、$s_{i}$、$s_{i+1}$（在取模条件下）同时取反）。请问，最多逆转 $2n$ 次，能否使所有火炬全部被点燃。如果能，输出对应的逆转次数，否则输出0。

• 小提示：$t$ 组数据。

2
5
00000
3
001

7
2 5 1 2 3 4 2
0

提示

For the first sample test case, the status of the torch will change like this: $00000$ $\to$ $11100$ $\to$ $01111$ $\to$ $10110$ $\to$ $01010$ $\to$ $00100$ $\to$ $00011$ $\to$ $11111$.