Trình soạn thảo (Editor)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Mô phỏng một dòng soạn thảo có độ dài vô hạn và một con trỏ. Ban đầu con trỏ ở vị trí đầu tiên. Có $N$ lệnh, được cho dưới dạng chuỗi ký tự:

• L: dịch con trỏ sang trái một vị trí; nếu đang ở vị trí đầu thì giữ nguyên.
• R: dịch con trỏ sang phải một vị trí.
• ( hoặc ): ghi đè ký tự tại vị trí hiện tại bằng ngoặc tương ứng.
• một chữ cái thường: ghi đè ký tự tại vị trí hiện tại bằng chữ cái; khi xét tính đúng của ngoặc, chữ cái được xem như không đóng góp cân bằng.

Sau mỗi lệnh, bỏ qua mọi chữ cái và xét dãy ngoặc hiện có. Nếu dãy ngoặc không đúng, in $-1$. Nếu đúng, in độ sâu lồng ngoặc lớn nhất, cũng chính là số màu nhỏ nhất cần dùng để mọi hai cặp ngoặc lồng nhau có màu khác nhau.

Input

Dòng đầu chứa $N$, $1\le N\le 10^6$.

Dòng thứ hai chứa chuỗi $N$ lệnh hợp lệ.

Output

In $N$ số trên một dòng, số thứ $i$ là kết quả sau khi xử lý $i$ lệnh đầu tiên.

Subtask

• 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$.

Ví dụ

Input

11
(R)R(R)Ra)c

Output

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

Giải thích

Sau mỗi lệnh, kết quả được tính trên toàn nội dung hiện tại. Chữ cái không ảnh hưởng cân bằng ngoặc nhưng vẫn có thể ghi đè một ngoặc cũ.