Problem 2. COW Splits

USACO 2026 First Contest, Bronze

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\le T\le 10^4$) and $k$ ($0 \le k \le 1$).

The first line of each test case has $N$ ($1 \le N \le 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 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 $i$th integer $x$ indicates that the $i$th letter of $S$ was deleted as part of the $x$th subsequence ($1 \le x \le 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 \le 10, N \le 6, k = 0$ Inputs 5-6: $k = 1$ Inputs 7-14: $k = 0$

Problem credits: Aakash Gokhale