Bessie is given a positive integer N and a string S of length 3N which is generated by concatenating N strings of length 3, each of which is a cyclic shift of "COW". In other words, each string will be "COW", "OWC", or "WCO".
String X is a square string if and only if there exists a string Y such that X=Y+Y where +represents string concatenation. For example, "COWCOW" and "CC" are examples of square strings but "COWO" and "OC" are not.
In a single operation, Bessie can remove any subsequence T from S where T is a square string. A subsequence of a string is a string which can be obtained by removing several (possibly zero) characters from the original string.
Your job is to help Bessie determine whether it is possible to transform S into an empty string. Additionally, if it is possible, then you must provide a way to do so.
Bessie is also given a parameter k which is either 0 or 1. Let M be the number of operations in your construction.
If k=0, then M must equal the minimum possible number of operations.
If k=1, then M can be up to one plus the minimum possible number of operations
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T, the number of independent test cases (1≤T≤104) and k (0≤k≤1).
The first line of each test case has N(1≤N≤105 ).
The second line of each test case has S.
The sum of N across all test cases will not exceed 105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output either one or two lines using the following procedure.
If it is impossible to transform S into an empty string, print −1 on a single line.
Otherwise, on the first line print M -- the number of operations in your construction. On the second line, print 3N space-separated integers. The ith integer x indicates that the ith letter of S was deleted as part of the xth subsequence (1≤x≤M).
SAMPLE INPUT:
3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC
SAMPLE OUTPUT:
-1
1
1 1 1 1 1 1 1 1 1 1 1 1
3
3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1
For the last test, the optimal number of operations is two, so any valid construction with either M=2 or M=3 would be accepted.
For M=3, here is a possible construction:
1.In the first operation, remove the last twelve characters. Now we're left with COWCOW.
2.In the second operation, remove the subsequence WW. Now we're left with COCO.
3.In the last operation, remove all remaining characters.
SAMPLE INPUT:
3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC
SAMPLE OUTPUT:
-1
1
1 1 1 1 1 1 1 1 1 1 1 1
2
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2
SCORING:
Inputs 3-4: T≤10,N≤6,k=0
Inputs 5-6: k=1
Inputs 7-14: k=0
Problem credits: Aakash Gokhale