310804: CF1890C. Qingshan Loves Strings 2
Description
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.
InputThe 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}$.
OutputFor 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.
ExampleInput6 2 01 3 000 4 1111 6 001110 10 0111001100 3 001Output
0 -1 -1 2 6 7 1 10 -1Note
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)
- $\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:
- $\texttt{001110}\underline{\texttt{01}}$
- $\texttt{0011100}\underline{\texttt{01}}\texttt{1}$
and get $s = \texttt{0011100011}$, which is good.
Output
晴山有一串仅包含'0'和'1'的字符串s。长度为k的字符串a如果是好的，当且仅当对于所有i=1,2,…,k，满足ai≠ak−i+1。晴山可以通过最多300次操作（可能为零次）来使s变得好，操作是在s的任意位置插入'01'。请判断是否可能使s变得好，如果可能，输出一系列操作使s变得好。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤100），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤100），表示字符串s的长度。
- 每个测试用例的第二行包含一个长度为n的字符串s，仅由'0'和'1'组成。
输出：
- 对于每个测试用例，如果无法使s变得好，输出-1。
- 否则，第一行输出p（0≤p≤300），表示操作的次数。
- 第二行输出p个整数，第i个整数xi（0≤xi≤n+2i−2）表示在当前s中插入'01'的位置。如果xi=0，表示在s的开始插入'01'；否则，表示在s的第xi个字符后插入'01'。
示例：
输入：
```
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
```
输出：
```
0
-1
-1
2
6 7
1
10
-1
```题目大意： 晴山有一串仅包含'0'和'1'的字符串s。长度为k的字符串a如果是好的，当且仅当对于所有i=1,2,…,k，满足ai≠ak−i+1。晴山可以通过最多300次操作（可能为零次）来使s变得好，操作是在s的任意位置插入'01'。请判断是否可能使s变得好，如果可能，输出一系列操作使s变得好。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤100），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤100），表示字符串s的长度。 - 每个测试用例的第二行包含一个长度为n的字符串s，仅由'0'和'1'组成。 输出： - 对于每个测试用例，如果无法使s变得好，输出-1。 - 否则，第一行输出p（0≤p≤300），表示操作的次数。 - 第二行输出p个整数，第i个整数xi（0≤xi≤n+2i−2）表示在当前s中插入'01'的位置。如果xi=0，表示在s的开始插入'01'；否则，表示在s的第xi个字符后插入'01'。 示例： 输入： ``` 6 2 01 3 000 4 1111 6 001110 10 0111001100 3 001 ``` 输出： ``` 0 -1 -1 2 6 7 1 10 -1 ```