CF1889A.Qingshan Loves Strings 2

Qingshan has a string $s$ which only contains $\texttt{0}$ and $\texttt{1}$.

A string $a$ of length $k$ is good if and only if

• $a_i \ne a_{k-i+1}$ for all $i=1,2,\ldots,k$.

For Div. 2 contestants, note that this condition is different from the condition in problem B.

For example, $\texttt{10}$, $\texttt{1010}$, $\texttt{111000}$ are good, while $\texttt{11}$, $\texttt{101}$, $\texttt{001}$, $\texttt{001100}$ are not good.

Qingshan wants to make $s$ good. To do this, she can do the following operation at most $300$ times (possibly, zero):

• insert $\texttt{01}$ to any position of $s$ (getting a new $s$).

Please tell Qingshan if it is possible to make $s$ good. If it is possible, print a sequence of operations that makes $s$ good.

青衫有一串只包含 0 和 1 的字符串 $s$。

长度为 $k$ 的字符串 $a$ 被称为好串，当且仅当对所有 $i = 1, 2, \ldots, k$，均满足

$$a_i \ne a_{k-i+1}.$$

（对 Div. 2 参赛者提示：该条件与题目 B 中的条件不同。）

例如，10、1010、111000 是好串，而 11、101、001、001100 不是好串。

青衫希望将 $s$ 变为好串。为此，她最多可执行 300 次（也可以为 0 次）如下操作：

• 在 $s$ 的任意位置插入子串 01（得到新的 $s$）。

请告诉青衫：是否可能将 $s$ 变为好串？若可能，请输出一组操作序列，使得最终 $s$ 成为好串。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n\le 100$) — the length of string $s$, respectively.

The second line of each test case contains a string $s$ with length $n$.

It is guaranteed that $s$ only consists of $\texttt{0}$ and $\texttt{1}$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1\le t\le 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n\le 100$），表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$。

保证字符串 $s$ 仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成。

For each test case, if it impossible to make $s$ good, output $-1$.

Otherwise, output $p$ ($0 \le p \le 300$) — the number of operations, in the first line.

Then, output $p$ integers in the second line. The $i$-th integer should be an index $x_i$ ($0 \le x_i \le n+2i-2$) — the position where you want to insert $\texttt{01}$ in the current $s$. If $x_i=0$, you insert $\texttt{01}$ at the beginning of $s$. Otherwise, you insert $\texttt{01}$ immediately after the $x_i$-th character of $s$.

We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most $300$ operations.

对于每个测试用例，如果无法使 $s$ 变为“好”的字符串，则输出 $-1$。

否则，在第一行输出 $p$（$0 \le p \le 300$）—— 所需操作的次数。

然后在第二行输出 $p$ 个整数。第 $i$ 个整数应为一个下标 $x_i$（$0 \le x_i \le n+2i-2$），表示你希望在当前字符串 $s$ 的哪个位置插入 $\texttt{01}$。若 $x_i = 0$，表示将 $\texttt{01}$ 插入到 $s$ 的开头；否则，表示将 $\texttt{01}$ 插入到 $s$ 的第 $x_i$ 个字符之后。

我们可以证明：在本题的约束条件下，若存在解，则必存在一个至多需要 $300$ 次操作的解。

In the first test case, you can do zero operations and get $s=\texttt{01}$, which is good.

Another valid solution is to do one operation: (the inserted $\texttt{01}$ is underlined)

1. $\texttt{0}\underline{\texttt{01}}\texttt{1}$

and get $s = \texttt{0011}$, which is good.

In the second and the third test case, it is impossible to make $s$ good.

In the fourth test case, you can do two operations:

1. $\texttt{001110}\underline{\texttt{01}}$
2. $\texttt{0011100}\underline{\texttt{01}}\texttt{1}$

and get $s = \texttt{0011100011}$, which is good.

在第一个测试用例中，你可以执行零次操作，得到 $s=\texttt{01}$，这是一个“好”字符串。

另一个合法的解法是执行一次操作（插入的 $\texttt{01}$ 用下划线标出）：

1. $\texttt{0}\underline{\texttt{01}}\texttt{1}$

从而得到 $s = \texttt{0011}$，这也是一个“好”字符串。

在第二个和第三个测试用例中，无法使 $s$ 变为“好”字符串。

在第四个测试用例中，你可以执行两次操作：

1. $\texttt{001110}\underline{\texttt{01}}$
2. $\texttt{0011100}\underline{\texttt{01}}\texttt{1}$

从而得到 $s = \texttt{0011100011}$，这是一个“好”字符串。