Cho một xâu độ dài chỉ gồm các kí tự ( và ), các kí tự được đánh số từ đến theo chiều từ trái qua phải.
Một dãy ngoặc đúng được định nghĩa như sau:
- Xâu rỗng là một dãy ngoặc đúng;
- Nếu là một dãy ngoặc đúng thì là một dãy ngoặc đúng;
- Nếu và là hai dãy ngoặc đúng thì là một dãy ngoặc đúng;
Cho truy vấn, mỗi truy vấn thuộc một trong hai loại sau:
- thay đổi kí tự dấu ngoặc ở vị trí của xâu kí tự thành kí tự dấu ngoặc ngược lại;
- in ra nếu xâu con từ vị trí đến vị trí là một dãy ngoặc đúng, in ra trong trường hợp ngược lại.
Dữ liệu vào:
- Dòng đầu chứa hai số nguyên dương là độ dài dãy ngoặc và số truy vấn;
- Dòng thứ hai chứa xâu ký tự độ dài chỉ gồm các ký tự
( và );
- dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại nêu trên.
Dữ liệu ra:
- Một chuỗi gồm các ký tự hoặc tướng ứng với câu trả lời mỗi truy vấn loại .
Ví dụ:
Dữ liệu vào:
8 7
()))(())
1 1 2
1 3 4
0 3
1 1 4
1 5 8
0 6
1 5 8
Dữ liệu ra:
Giới hạn:
- .
