题目描述

给定 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\)）。

输入输出样例 #1

输入 #1

3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

输出 #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

输入输出样例 #2

输入 #2

3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

输出 #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

说明/提示

对于最后一个测试用例，最优的操作次数是 \(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\)