青山有一个字符串$$$s$$$,它只包含$$$\texttt{0}$$$和$$$\texttt{1}$$$。
长度为 $$$k$$$ 的字符串 $$$a$$$ 是好的当且仅当
- $$$a_i \ne a_{k-i+1}$$$ 对于所有 $$$i=1,2,\ldots,k$$$。
对于分区。 2位参赛者,注意这个条件与问题B中的条件不同。
例如,$$$\texttt{10}$$$、$$$\texttt{1010}$$$、$$$\texttt{111000}$$$ 都不错,而 $$$\texttt{11}$$$、$$$\texttt{101}$$$、$$$\texttt{001}$$$、 $$$\texttt{001100}$$$ 不好。
青山想让$$$s$$$变得更好。为此,她最多可以执行以下操作 $$$300$$$ 次(可能为零):
- 将 $$$\texttt{01}$$$ 插入到 $$$s$$$ 的任意位置(获取新的 $$$s$$$)。
请告诉青山是否可以让$$$s$$$变得更好。如果可能的话,打印一系列使 $$$s$$$ 变好的操作。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n\le 100$$$) — 分别是字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个字符串 $$$s$$$,长度为 $$$n$$$。
保证 $$$s$$$ 仅由 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成。
输出
对于每个测试用例,如果不可能使 $$$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$$$,则在 $$$s$$$ 的开头插入 $$$\texttt{01}$$$。否则,您将在 $$$s$$$ 的第 $$$x_i$$$ 个字符之后插入 $$$\texttt{01}$$$。
我们可以证明,在这个问题的约束下,如果存在答案,则总有一个最多需要 $$$300$$$ 操作的答案。
示例
输入 #1
6 2 01 3 000 4 1111 6 001110 10 0111001100 3 001
输出 #1
0 -1 -1 2 6 7 1 10 -1
注意
在第一个测试用例中,您可以进行零运算并得到 $$$s=\texttt{01}$$$,这很好。
另一种有效的解决方案是执行一个操作:(插入的 $$$\texttt{01}$$$ 带下划线)
1.$$$\texttt{0}\下划线{\texttt{01}}\texttt{1}$$$
并得到 $$$s = \texttt{0011}$$$,这很好。
在第二个和第三个测试用例中,不可能使$$$s$$$ 变得良好。
在第四个测试用例中,可以进行两个操作:
1.$$$\texttt{001110}\underline{\texttt{01}}$$$
2.$$$\texttt{0011100}\下划线{\texttt{01}}\texttt{1}$$$
并得到 $$$s = \texttt{0011100011}$$$,这很好。