说明

时间限制：1 Sec 内存限制：256 MB 输入文件：bracket.in 输出文件：bracket.out

小明之前写过一个程序，用来寻找文本中括号对应的位置。

括号匹配的定义如下：

1. 在当前字符串中，如果存在 "(" 的紧后方是 ")"，就把这两个字符从字符串中删除。

2. 将删除后得到的新字符串作为处理对象，重复执行步骤 $1$，直到字符串变为空串。

对于初始给出的字符串，第 $i$ 个字符和第 $j$ 个字符会在上述过程中被一同删除，则称二者互为括号匹配。此时我们称 $j$ 为第 $i$ 个字符的匹配位置。

小明之前的程序只能逐个查询字符对应的匹配位置，使用起来很不方便。于是他打算重写程序，一次性求出所有字符的匹配位置。

给定仅由 "(" 和 ")" 构成、长度为 $N$ 的字符串 $S$。请输出字符串中每一个字符对应的匹配位置。

保证输入字符串中所有字符都存在对应的匹配位置。

输入格式

第一行一个整数 $N$。

第二行一个字符串 $S$。

输出格式

一共输出 $N$ 行。第 $i$ 行输出第 $i$ 个字符对应的匹配位置 $C_i$。

样例

样例 1

6
()(())

2
1
6
5
4
3

样例说明：

第 $1$ 个字符的匹配位置是 $2$，因此第 $1$ 行输出 $2$。

$N=6$，一共输出 $6$ 行。

数据范围

对于 40% 的数据，$N \le 10$。

对于 70% 的数据，$N \le 1000$。

对于 100% 的数据，$2 \le N \le 200000$，$|S| = N$。