MBRACKET - Shortest Regular Bracket

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mbracket


Xét dãy ngoặc chỉ gồm các ngoặc vuông và tròn - '( ) [ ]'.

Dãy ngoặc hợp lệ là :

1. '( )' , '[ ]' : hợp lệ.

2. A hợp lệ thì (A) và [A] hợp lệ.

3. A, B hợp lệ thì AB hợp lệ.

Ví dụ : '( ) ( ) [ ]', '( [ ] ) [ ( ) ]' và '[ ( ( ) ) ] [ ]' hợp lệ. Còn '(', '] [', '[ ( ]' and '( [ ) ]' không hợp lệ.

Cho 1 dãy ngoặc. Ở mỗi bước chèn thêm ngoặc vuông hoặc tròn vào đầu hoặc cuối. Với mỗi bước tính độ dài dãy ngoặc hợp lệ ngắn nhất gồm các ngoặc liên tiếp nhau mà chứa ngoặc mới được thêm vào.

Input

Dòng đầu là dãy ngoặc ban đầu, độ dài <= 100,000. Dòng tiếp theo là số nguyên N, 1 ≤ N ≤ 100,000, số thao tác.

N dòng tiếp theo, mỗi dòng gồm số nguyên A và kí tự C.
A = 0 thì C được chèn vào đầu xâu.
A = 1 thì C được chèn vào cuối xâu.

Output

Với mỗi bước i,1 <=i<=N, ghi độ dài ngắn nhất tìm được trên 1 dòng.

Sample

input 
[])
3
0 )
0 (
0 (
output
0
2
6

input
(]
3
1 )
0 )
0 (
output
0
0
2


Added by:psetter
Date:2009-02-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 04

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.