Problem Description

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 $\texttt{COW}$. In other words, each string will be $\texttt{COW}$, $\texttt{OWC}$, or $\texttt{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, $\texttt{COWCOW}$ and $\texttt{CC}$ are examples of square strings but $\texttt{COWO}$ and $\texttt{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

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

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

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

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

Hint

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 $\texttt{COWCOW}$.
2. In the second operation, remove the subsequence WW. Now we're left with $\texttt{COCO}$.
3. In the last operation, remove all remaining characters.

• Inputs 3-4: $T \le 10, N \le 6, k = 0$
• Inputs 5-6: $k = 1$
• Inputs 7-14: $k = 0$