为了与老朋友费尔南决斗,埃德蒙正在准备一种名为“的能量饮料”米什金劲量“。该饮料由长度为 $$$n$$$ 的字符串 $$$s$$$ 组成,仅由字符组成 L, I,和 T,对应饮料中三种不同物质的含量。
我们称这种饮料为 平衡 如果它含有相同数量的所有物质。为了增强自己的气场并确保决斗的胜利,埃德蒙必须通过以下操作使初始字符串保持平衡:
- 选择一个索引 $$$i$$$,使得 $$$s_i \neq s_{i+1}$$$ (其中 $$$i + 1$$$ 不得超过 当前 字符串的大小)。
- 插入一个字符 $$$x$$$,或者 L, I,或 T,在它们之间使得 $$$x \neq s_i$$$ 和 $$$x \neq s_{i+1}$$$ 。
通过表演帮助埃德蒙使饮料平衡并赢得决斗 不超过 $$$\textbf{2n}$$$ 操作。如果有多个解,则可以输出其中任意一个。如果不可能,您必须报告此情况。
输入
每个测试由多个测试用例组成。输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由字符组成 L, I,和 T.
输出
对于每个测试用例,如果没有解决方案,则输出 $$$-1$$$。否则,在第一行中输出单个整数 $$$m$$$ ($$$0 \le m \le 2n$$$) — 您执行的操作数。
那么接下来的$$$m$$$行的第$$$l$$$行应该包含一个整数$$$i$$$ ($$$1 \le i \lt n+l-1$$$),表示在$$$s_i$$$和$$$s_{i+1}$$$之间插入一个字符的操作。它必须满足 $$$s_i \neq s_{i+1}$$$。
如果有多个解,则可以输出其中任意一个。请注意,您不需要最小化此问题中的操作数量。
示例
输入复制
35TILII1L3LIT
输出复制
4 1 2 3 4 -1 0
注意
在第一个测试用例中,可以执行以下操作序列: 蒂利伊 $$$\右箭头$$$ TLILII $$$\右箭头$$$ TLTILII $$$\右箭头$$$ TLTLILII $$$\右箭头$$$ TLTLTILII.
在第二个测试用例中,无法执行任何操作,因此答案为$$$-1$$$。
在第三个测试用例中,初始字符串已具有等量的所有物质。