样例下载

题目描述

小明和你正在玩一个游戏。

有一个字符串池，池内只有三种字符串：ABC, BCA, CAB，每种字符串有无数个。

小明首先构造一个字符串。他从字符串池中选取了 N 个字符串，然后把这些字符串拼接成一个字符串，记为 S。显然，S 的长度为 3N，即 S 包含 3N 个字符。

然后小明让你把他构造的字符串清空，即通过若干次删除字符的操作把 S 变成空串。

但小明要求的删除操作非常奇特：每次删除操作，把你准备删除的字符按在 S 中的顺序拼接成一个字符串 T，你必须保证 T 是由两个相同的字符串拼接成的字符串，这次删除操作才可成功执行。

问：你能否将小明构造的字符串 S 清空？

如果不能，请输出一行一个整数 -1；如果能，请你输出你的操作方案，具体输出分两行：

• 第一行：一个整数 K，表示你删除操作的次数；
• 第二行：3N 个整数，第 i 个整数表示 S 的第 i 个字符在第几次操作时被删除。当然，你输出的这些整数应该介于 1 和 K 之间。

为了增加游戏难度，小明又给你提了一项要求：他告诉你一个参数 P，并且 P 要么为 0，要么为 1。如果 P = 0, 那么你必须要使用最少的操作次数将字符串清空；如果 P = 1，那么允许你操作的次数可以比最少的操作次数最多多一次。答案可能不唯一，按要求输出满足要求的任意一种可行方案即可。

每个测试点包含多组测试数据，而小明告诉你的参数 P 则是该测试点中所有测试数据通用的。

输入格式

第一行：两个整数 $T, P$，分别表示数据组数和小明给出的参数。

对于每组数据：

• 第一行：一个整数 $N$
• 第二行：一个字符串 $S$。

数据保证所有输入的 $N$ 之和 ≤ $10^5$。

输出格式

每组数据的答案占一行或两行，格式如题所述。

输入样例1

3 0
2
ABCABC
3
ABCBCACAB
4
ABCCABABCABC

输出样例1

1
1 1 1 1 1 1
-1
2
1 1 2 2 1 1 1 1 2 1 1 2

输入样例2

3 1
2
ABCABC
3
ABCBCACAB
4
ABCCABABCABC

输出样例2

1
1 1 1 1 1 1
-1
3
ABCCABABCABC
1 2 3 3 1 2 1 2 3 1 2 3

数据范围

共 100 分，具体如下：

20 分：$T ≤ 10, N ≤ 6, P = 0$

20 分：$1 ≤ T ≤ 10^4, 1 ≤ N ≤ 10^5, P = 1$

60 分：$1 ≤ T ≤ 10^4, 1 ≤ N ≤ 10^5, P = 0$

数据保证所有输入的 $N$ 之和 ≤ $10^5$。