描述

给定一个正整数 $N$ 和一个长度为 $3N$ 的字符串 $S$，该字符串由 $N$ 个长度为 3 的子串拼接而成，每个子串是 "COW" 的循环移位（即 "COW"、"OWC" 或 "WCO"）。定义一个字符串为“平方串”当且仅当它可以表示为某个字符串与其自身的连接，例如 "COWCOW" 是平方串，而 "COWO" 不是。

每次操作中，Bessie 可以从 $S$ 中删除任意一个作为子序列的平方串。你的任务是判断是否可以通过若干次操作将 $S$ 完全删空。如果可以，则根据参数 $k$ 输出一种合法的操作方案：

• 若 $k = 0$，操作次数必须是最小可能值；
• 若 $k = 1$，操作次数最多可以比最小值多 1。

对于每个测试用例，若无法清空字符串，输出 -1；否则先输出操作次数 $M$，再输出一个长度为 $3N$ 的整数序列，表示每个字符是在第几次操作中被删除的（操作编号从 1 到 $M$）。

输入输出格式

输入

第一行包含两个整数 $T$（测试用例数量）和 $k$（控制操作次数要求）。接下来每个测试用例包含两行：

• 第一行是一个整数 $N$；
• 第二行是一个长度为 $3N$ 的字符串 $S$。

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

输出

对每个测试用例：

• 如果无法清空字符串，输出 -1；
• 否则，第一行输出操作次数 $M$，第二行输出 $3N$ 个空格分隔的整数，表示每个字符被删除的操作编号。

样例

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

限制

• $1 \le T \le 10^4$
• $0 \le k \le 1$
• $1 \le N \le 10^5$
• 所有测试用例的 $N$ 之和不超过 $10^5$
• 时间限制：2.0 秒
• 空间限制：256MB