Editor

Source: Codeforces

Version: Phuoc Hung OJ Extended

Simulate an infinite editor line with a cursor. Initially the cursor points to the first position. A string of $N$ commands is given:

• L: move one position left; remain at the first position if already there.
• R: move one position right.
• ( or ): overwrite the current position with that bracket.
• a lowercase letter: overwrite the current position with that letter; letters contribute zero to bracket balance.

After each command, ignore letters and inspect the current bracket sequence. Print $-1$ if it is invalid. If it is valid, print the maximum nesting depth, which equals the minimum number of colors required so that nested bracket pairs use different colors.

Input

The first line contains $N$, $1\le N\le 10^6$.

The second line contains the string of $N$ valid commands.

Output

Print $N$ integers on one line; the $i$-th integer is the result after the first $i$ commands.

Subtasks

• Subtask 1 — 20%: $1\le N\le 50$.
• Subtask 2 — 30%: $1\le N\le 5000$.
• Subtask 3 — 50%: $1\le N\le 10^6$.

Examples

Input

11
(R)R(R)Ra)c

Output

-1 -1 1 1 -1 -1 1 1 1 -1 1

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.