题目描述

给定一个正整数 \(N\)，以及一个长度为 \(3N\) 的字符串 \(S\)。这个字符串是由 \(N\) 个长度为 \(3\) 的字符串依次拼接而成，并且每一段都一定是 "COW" 的循环位移之一，也就是说每一段只能是：

• COW
• OWC
• WCO

如果存在某个字符串 \(Y\)，使得 \(X = Y + Y\)，其中 \(+\) 表示字符串拼接，那么称字符串 \(X\) 为平方串。例如：

• COWCOW 是平方串
• CC 是平方串
• COWO 不是平方串
• OC 不是平方串

一次操作中，你可以从 \(S\) 中删除任意一个子序列 \(T\)，要求 \(T\) 本身是一个平方串。这里“子序列”指的是从原字符串中删去若干个字符后，按原相对顺序保留下来的字符串。

请判断能否把 \(S\) 通过若干次操作删成空串。如果可以，还需要给出一种可行方案。

题目还给出参数 \(k\)，其值只可能是 \(0\) 或 \(1\)。设你构造出的方案使用了 \(M\) 次操作，则必须满足：

• 如果 \(k = 0\)，那么 \(M\) 必须是最小可能值；
• 如果 \(k = 1\)，那么 \(M\) 至多比最优值大 \(1\)。

输入格式

第一行包含两个整数 \(T\) 和 \(k\)，分别表示测试组数与参数，满足 \(1 \le T \le 10^4\)，\(0 \le k \le 1\)。

接下来有 \(T\) 组测试数据，每组格式如下：

• 第一行一个整数 \(N\)，满足 \(1 \le N \le 10^5\)
• 第二行一个字符串 \(S\)

保证所有测试数据中 \(N\) 的总和不超过 \(10^5\)。

输出格式

对于每组测试数据，按如下方式输出。

如果无法删成空串，输出一行 -1。

否则：

• 第一行输出 \(M\)，表示你的方案使用的操作次数；
• 第二行输出 \(3N\) 个整数。第 \(i\) 个整数 \(x_i\) 表示原字符串中第 \(i\) 个字符是在第 \(x_i\) 次操作中被删除的，且必须满足 \(1 \le x_i \le M\)。

样例 1

输入

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

说明

对于最后一个测试，最优操作次数其实是 \(2\)，因此任何满足 \(M=2\) 或 \(M=3\) 的合法构造都可以被接受。

上面的样例中给出的是 \(M=3\) 的一种做法：

• 第一次删除最后 \(12\) 个字符，剩下 COWCOW
• 第二次删除子序列 WW，剩下 COCO
• 第三次删掉剩余所有字符

样例 2

输入

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

数据范围

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

命题信息

原题命题：Aakash Gokhale