Migrated from Lutece 2363 利姆露的魔法序列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

利姆露现在想知道一个奇怪魔法序列的含义，于是她把这个任务交给了大贤者。

这个魔法序列由 $n$ 个字符组成，仅包含 L，R，小写拉丁字母和括号（即 ‘(’ 和 ‘)’），表达对一个空白字符串的操作（因为是空白字符串，所以最初操作位置在哪里都一样），其中

1. L 表示当前操作位置左移一位。
2. R 表示当前操作位置右移一位。
3. 其余任何小写拉丁字母或括号表示将当前操作位置修改为该字符。

大贤者知道这个操作产生的序列对应一个魔法，当序列中括号不合法时，魔法会失败；而括号序列合法时，括号的最大嵌套重数就是魔法的强度。

现在大贤者想知道这个过程中每一步产生的序列对应的魔法是一个失败的魔法还是一个成功的魔法，若是一个成功的魔法，则其威力是多少？你能够帮忙完成这件事吗？

Input

第一行一个非负整数 $n$，表示奇怪魔法序列的字符数。 接下来一行是一个长为 $n$ 的字符串（仅含 L，R，小写拉丁字母和括号）

Output

输出一行 $n$ 个整数表示的答案（用空格隔开，末尾换行），依次表示该次操作后产生的序列对应的是一个成功魔法（输出魔法的强度）还是一个失败魔法（输出 $-1$）。

Samples

10
k(R)v(R)R)

0 -1 -1 1 -1 -1 -1 -1 -1 2

15
(R)R(R)R)LLLLL(

-1 -1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 2

Constraints

$0<n\le 10^6$

Note

合法括号序列的定义是（略去字母和空格）：

1. 空序列是合法括号序列。
2. 如果 S 是合法括号序列，那么 (S) 是合法括号序列。
3. 如果 A 和 B 都是合法括号序列，那么 AB 是合法括号序列。

样例二解释如下(下划线表当前操作位置)：

• _
• $\underline{(}$ -1
• (_ -1
• ($\underline{)}$ 1
• ()_ 1
• ()$\underline{(}$ -1
• ()(_ -1
• ()($\underline{)}$ 1
• ()()_ 1
• ()()$\underline{)}$ -1
• ()($\underline{)}$) -1
• ()$\underline{(}$)) -1
• ($\underline{)}$()) -1
• $\underline{(}$)()) -1
• _()()) -1
• $\underline{(}$()()) 2

Resources

2020 UESTC ICPC Training for Data Structures