Problem Statement

Orino once wrote a program that finds the matching positions of brackets in a text (No.22 Bracket Matching).

Bracket matching is defined as follows:

1. If the given string contains a "(" immediately followed by a ")", delete those two characters from the string.
2. Treat the string after the deletion as a new string and repeat the process of 1., continuing until the string becomes empty.

Then, with positions considered in the initially given string, the \(j\)-th character that is deleted together with the \(i\)-th character is its "bracket match".
Here, we call \(j\) the "matching position" of the \(i\)-th character.

The program Orino wrote before could tell the matching position of a specified character, but he found it inconvenient that characters had to be specified one at a time.
So, Orino decided to rewrite the program so that it reports the matching positions of all characters in the text at once.

You are given a string \(S\) of \(N\) characters consisting only of "(" and ")".
For each of the characters in \(S\), output its matching position.
It is guaranteed that every character in the given string has a bracket match.

Input

\(N\)
\(S\)

The first line contains \(N\), the number of characters.
The second line contains the string \(S\).
\(2 \le N \le 200000\)
\(|S| = N\)

Output

\(C_1\)
\(C_2\)
\(\vdots\)
\(C_N\)

From line \(1\) to line \(N\), on line \(i\), output the matching position \(C_i\) of the \(i\)-th character.

Sample