说明

我们定义一个正确的括号序列为满足以下任一条件的字符串：

• 它是一个空字符串。
• 它由 $($、$A$、$)$ 按此顺序连接而成，其中 $A$ 是一个正确的括号序列。
• 它由 $A$ 和 $B$ 按此顺序连接而成，其中 $A$ 和 $B$ 都是非空的正确括号序列。

给定一个长度为 $N$ 的字符串 $S$，由字符 $($ 和 $)$ 组成。

对于每个满足 $0 \leq i \leq N$ 的 $i$，定义字符串 $T_i$ 为：将 $S$ 的长度为 $N - i$ 的后缀与 $S$ 的长度为 $i$ 的前缀的反转字符串按此顺序连接而得到的字符串。也就是说，如果我们用 $S_i$ 表示 $S$ 的第 $i$ 个字符，那么 $T_i$ 由字符 $S_{i+1}, S_{i+2}, \ldots, S_N, S_i, \ldots, S_2, S_1$ 按顺序排列而成。

对于每个满足 $0 \leq i \leq N$ 的 $T_i$，解决以下问题：

• 考虑一种操作：将 $T_i$ 中的一个字符替换为 $($ 或 $)$。求使 $T_i$ 成为一个正确的括号序列所需的最少操作次数。

输入格式

输入以如下格式给出：

• $2 \leq N \leq 200,000$
• $N$ 是偶数。
• $S$ 是一个长度为 $N$ 的字符串，仅由 $($ 和 $)$ 组成。

输出格式

输出 $N + 1$ 行。在第 $i + 1$ 行输出 $T_i$ 的答案。

4
()()

0
2
2
2
2

6
)))(((

4
2
2
0
0
0
0

8
)())())(

3
1
3
1
1
1
1
1
1

提示

翻译由 DeepSeek V3.2 完成