409706: GYM103688 H Kanbun

Paulliant is a linguist. Recently he received an article written in language A and he was told to translate it into language B. The two languages only differ in word order, so, Paulliant decided to translate by redefining the reading order of the articles, and came up with the following method.

Suppose that the article consists of $$$n$$$ words, numbered as $$$1,2,3\cdots n$$$. Paulliant generated a string $$$str$$$ consisting of only '(', ')' and '-', whose length is also $$$n$$$. The string must satisfy the rule of bracket matching. Formally speaking, define $$$s_{(i}$$$ and $$$s_{)i}$$$ , representing the number of character '(' or ')' within the first $$$i$$$ characters of the string, respectively, there is $$$s_{(i} \geq s_{)i}$$$ for every $$$1\leq i\leq n$$$ and $$$s_{(n}=s_{)n}$$$.

The process to read the article obeys the following rules.

(1) The process starts from the first word.

(2) For the $$$i$$$-th word, if $$$str_i$$$ is '-' or ')', then read the $$$i$$$-th word directly, and jump to the $$$(i+1)$$$-th word.

(3) For the $$$i$$$-th word, if $$$str_i$$$ is '(', then find the matching right bracket of it. Supposing it to be $$$str_j$$$, read the $$$(i+1)$$$-th to $$$j$$$-th word, then read the $$$i$$$-th word, and finally jump to the $$$(j+1)$$$-th word.

(4) If we are to read the $$$(n+1)$$$-th word (obviously it doesn't exist), the process ends.

Note that the process is recursive, meaning that when reading the $$$(i+1)$$$-th to $$$j$$$-th word in rule (2), it still follows the four rules.

For example,

· If $$$n=4$$$, $$$str$$$ is "(-)-", the reading order will be 2, 3, 1, 4.

· If $$$n=7$$$, $$$str$$$ is "-((-)-)", the reading order will be 1, 4, 5, 3, 6, 7, 2.

Now, give you the number of words $$$n$$$, and the string $$$str$$$ Paulliant generated. Your task is to print the reading order following the four rules. It can be proved that the reading order should be a permutation of numbers from $$$1$$$ to $$$n$$$.

​The first line contains a single integer $$$n\ (3\leq n\leq 10^5)$$$ — the number of words.

​The second line contains a string $$$str$$$ of $$$n$$$ characters. It consists of $$$n$$$ characters of only '(', ')', '-', and it's guaranteed to satisfy the rules of bracket matching.

​Output a line consisting of $$$n$$$ integers which represent the reading order, it should be a permutation of numbers from $$$1$$$ to $$$n$$$. The $$$n$$$ integers are separated by spaces.

4
(-)-

2 3 1 4

7
-((-)-)

1 4 5 3 6 7 2

14
((-)-()--)(-)-

3 4 2 5 7 6 8 9 10 1 12 13 11 14