Page not loading? Try clicking here.
Placeholder

#8841
Special judge
Subtask

COW Splits 1s 1024MB

Problems

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

The first line contains T, the number of independent test cases (1≤T≤10^4) and k

(0≤k≤1).

The first line of each test case has N (1≤N≤10^5).

The second line of each test case has S.

The sum of N across all test cases will not exceed 10^5.


Output

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).


Subtask

# Score Condition
#120

T≤10,\ N≤6,\ k=0

#230

k=1

#350

k=0


Example #1

3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC
-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.


Example #2

3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC
-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


Source

USACO 2026 First Contest, Bronze

You must sign in to write code.