解题思路

把已经能够两两匹配的括号先消掉，问题就会变得非常简单。

设用栈扫描整个字符串 $s$：

• 遇到 '('，下标入栈；
• 遇到 ')'：

题目内容

我们称一个括号序列为“平衡的括号序列”，当且仅当满足以下归纳定义：

空串是平衡的；

若字符串 $A$ 是平衡的，则“($A$)”是平衡的；

若字符串 $A$ 与 $B$ 均是平衡的，则“$AB$”（连接）是平衡的。 例如：括号序列 $()$ 与 $(())$ 是平衡的；而 $)、)()、($ 不是。

给定一个只由 $($ 与 $)$ 组成、长度为 $n$ 的字符串 $s$ ($n$ 为偶数)。你可以进行若干次如下操作： 选择一个下标 $i (1 <= i <= n)$，将字符 $s_i$ 的“类型”镜像翻转：若 $s_i = '('$ 则变为 $')'$；若 $s_i = ')'$ 则变为 $'('$。其余位置保持不变。

请你计算使 $s$ 变为平衡括号序列所需的最少操作次数，并输出任意一组达到最少次数的操作下标序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T (1 <= T <= 10^5)$ 表示数据组数。每组测试数据描述如下：

第一行输入一个偶数 $n (2 <= n <= 2 * 10^5)$；

第二行输入一个长度为 $n$ 的字符串 $s$ (仅包含字符 $'('$ 与 $')')$。

保证所有测试中 $n$ 的总和不超过 $2 * 10^5$。

输出描述

对于每组测试数据，输出两行：

第一行输出一个整数 $k$，表示最少操作次数；

第二行输出 $k$ 个整数 $p_1, p_2, ..., p_k (1 <= p_j <= n)$，表示依次在位置 $p_j$ 处进行单点镜像翻转。

若 $k = 0$，第二行留空即可。 若存在多组最优方案，输出任意一组。

样例1

输入

3
2
)(
4
()()
4
))((

输出

2
1 2
0

2
1 4

说明

样例一：

依次翻转位置 $1, 2，)( -> ()$，最少 $2$ 次。

样例二：$s$ 已是平衡串，$k = 0$，第二行留空。

样例三：翻转位置 $1$ 与 $4$，$))(( -> ()()$，最少 $2$ 次。