题目内容

在一栋大楼的电梯系统中，运行记录由字符 U（上升一层）和 D（下降一层）组成。一次合法的运行记录需满足：电梯从地面（第 0 层）出发，最终回到地面，并且中途从未进入地下层。更形式化地，一个合法的运行记录序列定义如下：

• 空序列是合法的。
• 如果序列 $A$ 合法，则 U + $A$ + D 是合法的。
• 如果序列 $A$ 和 $B$ 均合法，则 $A$ 与 $B$ 连接形成的序列是合法的。

等价地，一个合法的序列中 U 与 D 的数量相等，且任意前缀中 U 的数量不少于 D 的数量。

现在给出一个由 U 和 D 组成、长度为偶数 $n$ 的序列，可能不合法。你可以进行任意次修正操作：每次操作选择一个位置 $i$ ($1 \le i \le n$)，将该位置的字符翻转为另一个字符（U 变为 D，或 D 变为 U）。请你求出使得序列变为合法所需的最少操作次数，并输出任意一种达到该最少次数的操作位置序列（位置从 $1$ 开始编号）。

约束条件：

• 测试数据组数 $T$ 满足 $1 \le T \le 10^5$。
• 序列长度 $n$ 为偶数，满足 $2 \le n \le 2 \times 10^5$。
• 所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。
• 字符串仅包含字符 U 和 D。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来每组数据包含两行：第一行一个偶数 $n$，表示序列长度；第二行一个长度为 $n$ 的字符串 $s$，仅由字符 U 和 D 组成。

输出描述

对于每组数据，输出两行：第一行一个整数 $k$，表示最少操作次数；第二行输出 $k$ 个整数，表示需要翻转的操作位置（顺序任意）。若 $k = 0$，则第二行留空（输出一个空行）。

样例1

输入

1
4
(())

输出

0

说明

序列 (()) 本身已经是合法的括号序列（可将 ( 视为上升一层，) 视为下降一层）。电梯从地面出发，依次上升两次再下降两次，最终回到地面且中途从未进入地下层，因此不需要任何翻转操作。最少操作次数为 0。

样例2

输入

1
4
))))

输出

2
1 2

说明

序列 )))) 由 4 个下降操作组成，没有任何上升操作。利用栈进行匹配扫描后，未匹配的右括号位置为 1, 2, 3, 4，未匹配的左括号数量为 0。未匹配右括号有 $a = 4$ 个，最少需要翻转 $\lceil a/2 \rceil = \lceil 4/2 \rceil = 2$ 个右括号。选择翻转前两个位置 1 和 2 后，序列变为 (())，是一个合法的括号序列，操作次数 2 达到最优。

样例3

输入

1
6
)()(())

输出

2
1 4

说明

序列 )()(()) 的长度为 6。扫描过程中，位置 2 的 ( 与位置 3 的 ) 匹配，位置 5 的 ( 与位置 6 的 ) 匹配；消去这些可匹配部分后，剩余未匹配的右括号为位置 1，未匹配的左括号为位置 4。因此 $a = 1$，$b = 1$，最少需要翻转 $\lceil 1/2 \rceil + \lceil 1/2 \rceil = 2$ 个字符。翻转第 1 个位置（多余的 )）和第 4 个位置（多余的 (）后，序列变为 (())()，满足合法运行记录的要求。