35327번 - COW Splits 스페셜 저지다국어

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

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

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