Một dãy ngoặc đúng là một xâu ký tự được định nghĩa đệ quy như sau:

• Xâu rỗng (không có ký tự nào) là một dãy ngoặc đúng
• Nếu \(X\) là một dãy ngoặc đúng thì \((X)\) cũng là một dãy ngoặc đúng, ở đây \((X)\) là xâu tạo thành bằng cách chèn thêm ký tự ( vào đầu và ký tự ) vào cuối xâu \(X\)
• Nếu \(Y\) và \(Z\) là hai dãy ngoặc đúng thì \(YZ\) cũng là một dãy ngoặc đúng, ở đây \(YZ\) là xâu tạo thành bằng cách nối xâu \(Z\) vào sau xâu \(Y\)

Những xâu ký tự không thể xây dựng được theo quy tắc trên không phải là dãy ngoặc đúng.

Ví dụ: ()() và (()) là những dãy ngoặc đúng nhưng (() và ())( không phải là dãy ngoặc đúng.

Với một xâu ký tự đó đại diện chỉ gồm các ký tự ∈ {'(', ')'}, ta gọi trong số của xâu đó số ký tự ít nhất trong xâu cần thay đổi (từ ( thành ) hoặc từ ) thành () để ta thu được một dãy ngoặc đúng.

Bắt đầu với xâu ký tự \(S\) rỗng, người ta thực hiện tuần tự \(m\) lệnh (đánh số từ \(1\) tới \(m\)) thuộc một trong hai loại:

• Loại 1 \((T)\): Ở đây \(T\) là một xâu gồm 2 ký tự ∈ {'(', ')'}. Lệnh này thêm xâu \(T\) vào cuối xâu \(S\) để thu được xâu \(S\) mới. Lệnh đầu tiên trong dãy lệnh luôn là lệnh loại 1.
• Loại 2 \((U)\): Ở đây \(U\) là một số nguyên dương nhỏ hơn chỉ số lệnh hiện tại. Lệnh này phục hồi lại xâu \(S\) như tình trạng trước khi thực hiện lệnh thứ \(U\).

Hãy cho biết trong số của xâu \(S\) sau mỗi lệnh.

Input

• Dòng 1 chứa số nguyên dương \(m \leq 10^6\) là số lệnh
• \(m\) dòng tiếp theo chứa thông tin về một lệnh theo mô tả trên.

Output

• Sau mỗi thao tác được thực hiện, in ra trong số hiện tại của xâu \(S\) trên một dòng.

Example

9
()
((
((
2
))
4
))
))
)(

0
1
2
0
1
2
1
0
2