Bối cảnh của bài toán này giống với Bài F. Những điểm khác biệt so với Bài F được gạch chân.

Bạn được cho một xâu $S$ có độ dài $N$ chỉ gồm các ký tự ( và ).

Hãy trả lời $Q$ truy vấn. Ở truy vấn thứ $i$, bạn được cho hai số nguyên $L_i$ và $R_i$. Hãy giải bài toán sau:

Gọi $X$ là xâu con của $S$ từ ký tự thứ $L_i$ đến ký tự thứ $R_i$. Xét việc chọn một số nguyên dương $k$ rồi chọn một xâu con $Y$ của xâu thu được bằng cách ghép $k$ bản sao của $X$ lại với nhau. Ở đây, $Y$ phải là một dãy ngoặc đúng. $Y$ được phép là xâu rỗng.

Hãy xác định xem có tồn tại độ dài lớn nhất có thể cho $Y$ hay không, và nếu tồn tại, hãy tìm giá trị lớn nhất đó.

Dãy ngoặc đúng

Một dãy ngoặc đúng là một xâu có thể rút gọn thành xâu rỗng bằng cách lặp lại việc xóa xâu con liên tiếp () không hoặc nhiều lần.

Dữ liệu vào

Dữ liệu vào được cung cấp từ Đầu vào chuẩn theo định dạng sau:

N Q
S
L_1 R_1
L_2 R_2
...
L_Q R_Q

• $N, Q, L_i, R_i$ là các số nguyên.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ là một xâu có độ dài $N$ chỉ gồm ( và ).
• $1 \le L_i \le R_i \le N$

Kết quả

In ra $Q$ dòng. Ở dòng thứ $i$, in ra độ dài lớn nhất có thể của $Y$ trong truy vấn thứ $i$ nếu nó tồn tại, và -1 trong trường hợp ngược lại.

Ví dụ

Ví dụ đầu vào 1

4 3
()((
2 3
1 4
3 4

Ví dụ đầu ra 1

-1
2
0

Ghi chú

• Ở truy vấn thứ nhất, $X =$ )(. Với mọi số nguyên dương $k$, nếu ta ghép $k$ bản sao của $X$ rồi xóa ký tự đầu tiên và ký tự cuối cùng, ta thu được một dãy ngoặc đúng có độ dài $2k - 2$. Do đó, không tồn tại độ dài lớn nhất có thể cho $Y$, vì vậy bạn cần in ra -1.
• Ở truy vấn thứ hai, $X =$ ()((. Có thể chứng minh rằng độ dài lớn nhất có thể của $Y$ là $2$. Do đó, hãy in ra 2.
• Ở truy vấn thứ ba, $X =$ ((. Độ dài lớn nhất có thể của $Y$ là $0$, vì vậy hãy in ra 0. Lưu ý rằng $Y$ có thể là xâu rỗng.