E. PQUERY - Dãy ngoặc

Một dãy dấu ngoặc đúng là một dãy các ký tự ( và ) được định nghĩa như sau:

• Dãy rỗng (không có ký tự nào) là một dãy dấu ngoặc đúng;
• Nếu là một dãy dấu ngoặc đúng thì là dãy dấu ngoặc đúng. Dấu ngoặc mở và dấu ngoặc đóng hai bên dãy được gọi là tương ứng với nhau;
• Nếu và là hai dãy dấu ngoặc đúng thì là dãy dấu ngoặc đúng.

Cho xâu ký tự chỉ gồm các ký tự ( và ), xét một dãy gồm thao tác thuộc một trong hai dạng:

• Nếu ký tự đang là dấu mở ngoặc (, nó sẽ được thay bởi dấu đóng ngoặc ) và ngược lại, nếu ký tự đang là dấu đóng ngoặc, nó sẽ được thay bằng dấu mở ngoặc.
• Cho biết độ dài dãy ngoặc đúng dài nhất tạo thành từ các ký tự liên tiếp trong xâu bắt đầu từ vị trí . Tức là tìm độ dài lớn nhất mà xâu là một dãy ngoặc đúng.

Yêu cầu: Hãy trả lời tất cả các truy vấn loại .

Dữ liệu vào:

• Dòng đầu chứa xâu ký tự độ dài ;
• Dòng thứ hai chứa số nguyên dương là số thao tác;
• dòng tiếp theo, mỗi dòng chứa ký tự đầu dòng cho biết loại thao tác, tiếp theo là dấu cách và một số nguyên chỉ ra vị trí tương ứng với thao tác .

Dữ liệu ra:

• Úng với mỗi thao tác ghi ra một số nguyên duy nhất là kết quả trả lời trên một dòng.

Ví dụ:

Dữ liệu vào:

)((())()
6
Q 3
C 7
Q 2
Q 1
C 1
Q 1

Dữ liệu ra:

6
6
0
8