Skip to content
Sign in

COW Splits

UnratedSpecial judge
English

Language

Contribute a translation
Time limit
2000 ms
Memory limit
256 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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

Scoring

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

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

Examples

Sample input 1
3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC
Sample output 1
-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
Sample input 2
3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC
Sample output 2
-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

Notes

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.

Tags

No tags yet

Source