To read the problem statement in English, choose the language using the flag on the navigation bar.

Một xâu kí tự được gọi là chuỗi ngoặc nếu như trong xâu kí tự chỉ có kí tự '(' hoặc ')'.

Một chuỗi ngoặc ~X~ được gọi là đơn giản nếu như:

• hoặc ~X~ bằng "()",

• hoặc ~X~ có dạng "(Y)", với ~Y~ là một chuỗi ngoặc đơn giản.

Ví dụ, các chuỗi ngoặc (), (()) và (((()))) là các chuỗi ngoặc đơn giản, trong khi ()(), )(, (())() hay (()()) thì không phải.

Xét một chuỗi ngoặc ~S~. Nếu như trong ~S~ tồn tại một xâu con là chuỗi ngoặc đơn giản, ta có thể thực hiện thao tác xóa chuỗi ngoặc đơn giản bất kì trong xâu ~S~ đi. Ta gọi độ phức tạp của một chuỗi ngoặc ~S~ là số lần thực hiện thao tác ít nhất cần thực hiện để xâu ~S~ không chứa xâu con nào là chuỗi ngoặc đơn giản.

Cho một chuỗi ngoặc ~P~ có độ dài ~n~ và ~q~ truy vấn, truy vấn thứ ~i~ sẽ có dạng ~(l_i, r_i)~, hãy tính độ phức tạp của xâu ~P_{l_i \ldots r_i}~, tức xâu kí tự tạo bởi các kí tự của xâu ~P~ từ vị trí ~l_i~ đến ~r_i~.

Một xâu kí tự ~a~ được gọi là xâu con của xâu kí tự ~b~, nếu như ~a~ có thể thu được bằng cách xóa từ ~b~ một vài kí tự ở đầu (có thể là không kí tự nào), và xóa đi một vài kí tự ở cuối (có thể là không kí tự nào).

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n \le 10^5~, ~1 \le q \le 10^5~) lần lượt là độ dài xâu ~P~ và số lượng truy vấn cần trả lời.

Dòng tiếp theo chứa chuỗi ngoặc ~P~ có độ dài ~n~.

Dòng thứ ~i~ trong số ~q~ dòng tiếp theo chứa hai số nguyên ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le n~), thể hiện truy vấn thứ ~i~ của bài toán.

Output

In ra ~q~ dòng, dòng thứ ~i~ là độ phức tạp của xâu con ~P_{l_i \ldots r_i}~.

Scoring

• Subtask 1, tương ứng với ~40~ điểm, có ~n, q \le 1000~.

• Subtask 2, tương ứng với ~60~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán sẽ có ~100~ điểm.

Sample Input 1

8 3
(()))(()
1 8
1 5
2 8

Sample Output 1

2
1
2

Notes

Ở truy vấn đầu tiên, xâu con ta cần tìm độ phức tạp là xâu ~P_{1\ldots 8}~ hay "(()))(()". Ta có thể thực hiện các thao tác biến đổi sau (xóa các kí tự bị gạch ngang):

Có thể thấy đây là một cách xóa tối ưu, và ~2~ thao tác là số thao tác ít nhất cần thực hiện.