题目描述

给定 Bessie 一个正整数 $N$ 和一个长度为 $3N$ 的字符串 $S$，该字符串是由 $N$ 个长度为 $3$ 的字符串拼接而成，每个字符串都是 $\texttt{COW}$ 的一个循环移位。换句话说，每个字符串将是 $\texttt{COW}$、$\texttt{OWC}$ 或 $\texttt{WCO}$ 中的一个。

字符串 $X$ 是一个平方串，当且仅当存在一个字符串 $Y$ 使得 $X = Y + Y$，其中 $+$ 表示字符串拼接。例如，$\texttt{COWCOW}$ 和 $\texttt{CC}$ 是平方串的例子，但 $\texttt{COWO}$ 和 $\texttt{OC}$ 不是。

在一次操作中，Bessie 可以从 $S$ 中移除任意一个子序列 $T$，其中 $T$ 是一个平方串。一个字符串的子序列是指通过从原字符串中删除若干（可以是零个）字符而得到的字符串。

你的任务是帮助 Bessie 判断是否可能将 $S$ 转化为空字符串。此外，如果可能，你必须提供一种实现方法。

Bessie 还会收到一个参数 $k$，其值为 $0$ 或 $1$。设 $M$ 为你构造方案中的操作次数。

• 如果 $k = 0$，则 $M$ 必须等于可能的最小操作次数。
• 如果 $k = 1$，则 $M$ 最多可以比可能的最小操作次数多 $1$。

输入格式

第一行包含 $T$，表示独立测试用例的数量（$1\le T\le 10^4$），以及 $k$（$0 \le k \le 1$）。

每个测试用例的第一行有 $N$（$1 \le N \le 10^5$）。

每个测试用例的第二行有 $S$。

所有测试用例的 $N$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，按照以下流程输出一行或两行。如果不可能将 $S$ 转化为空字符串，则在一行中输出 $-1$。

否则，在第一行输出 $M$——你构造方案中的操作次数。在第二行，输出 $3N$ 个由空格分隔的整数。第 $i$ 个整数 $x$ 表示 $S$ 的第 $i$ 个字母是在第 $x$ 次操作中被删除的（$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

提示

对于最后一个测试用例，最优的操作次数是 $2$，因此任何 $M=2$ 或 $M=3$ 的有效构造方案都会被接受。

对于 $M=3$，这里是一种可能的构造方案：

1. 在第一次操作中，移除最后 $12$ 个字符。现在剩下 $\texttt{COWCOW}$。
2. 在第二次操作中，移除子序列 WW。现在剩下 $\texttt{COCO}$。
3. 在最后一次操作中，移除所有剩余字符。

---

• 输入 $3$-$4$：$T \le 10, N \le 6, k = 0$
• 输入 $5$-$6$：$k = 1$
• 输入 $7$-$14$：$k = 0$

翻译由 DeepSeek V3 完成