# [Solution] Qingshan Loves Strings 2 Solution Codeforces

## [Solution] Qingshan Loves Strings 2 Solution Codeforces

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Qingshan has a string s which only contains 00 and 11.

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

• aiaki+1��≠��−�+1 for all i=1,2,,k�=1,2,…,�.

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

For example, 101010101010111000111000 are good, while 1111101101001001001100001100 are not good.

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

• insert 0101 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.

### Input [Solution] Qingshan Loves Strings 2 Solution Codeforces

The input consists of multiple test cases. The first line contains a single integer t (1t1001≤�≤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 (1n1001≤�≤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 00 and 11.

#### Output [Solution] Qingshan Loves Strings 2 Solution Codeforces\$

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

Otherwise, output p (0p3000≤�≤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 xi�� (0xin+2i20≤��≤�+2�−2) — the position where you want to insert 0101 in the current s. If xi=0��=0, you insert 0101 at the beginning of s. Otherwise, you insert 0101 immediately after the xi��-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 300300 operations.

Example
input

Copy
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
output

Copy
0

-1
-1
2
6 7
1
10
-1


### Note [Solution] Qingshan Loves Strings 2 Solution Codeforces

In the first test case, you can do zero operatiaon and get s=01�=01, which is good.

Another valid solution is to do one operation: (the inserted 0101 is underlined)

1. 001–––1001_1

and get s=0011�=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. 00111001–––00111001_
2. 001110001–––1001110001_1

and get s=0011100011�=0011100011, which is good.