Cho một xâu ~S~ độ dài ~N~ chỉ gồm các ký từ '(' và ')'.

Bạn được cho ~Q~ truy vấn, truy vấn thứ ~i~ thuộc một trong hai dạng sau:

• ~1~ ~x~: Nếu ~S_x~ là '(' thì ~S_x~ sẽ trở thành ')'. Nếu ~S_x~ là ')' thì ~S_x~ sẽ trở thành '('.

• ~2~ ~x~: Tìm độ dài dãy ngoặc đúng dài nhất bắt đầu tại vị trí ~x~.

Ta định nghĩa một dãy ngoặc đúng như sau:

• Nếu ~A~ rỗng thì ~A~ là một dãy ngoặc đúng

• Nếu ~A~ là một dãy ngoặc đúng thì ~(A)~ cũng là một dãy ngoặc đúng

• Nếu ~A~, ~B~ là dãy ngoặc đúng thì ~AB~ cũng là một dãy ngoặc đúng

Một vài ví dụ cho dãy ngoặc đúng: "(())()", "((()))", "()()()".

Input

Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 5 \cdot 10^5)~.

Dòng thứ hai chứa xâu ~S~.

~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~t~ và ~x~ ~(t \in {1, 2}, 1 \le x \le N)~.

Output

Với mỗi truy vấn ~t = 2~, in ra độ dài dãy ngoặc đúng dài nhất bắt đầu tại vị trí ~x~ trên một dòng.

Scoring

Sample Input 1

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

Sample Output 1

0
2
2

Sample Input 2

8 6
)((())()
2 3
1 7
2 2
2 1
1 1
2 1

Sample Output 2

6
6
0
8

Notes

Trong test ví dụ đầu tiên:

• Ở truy vấn thứ ~1~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 1~ là ~\varnothing~.

• Ở truy vấn thứ ~2~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 2~ là "()".

• Ở truy vấn thứ ~3~, ~S~ đổi thành "())".

• Ở truy vấn thứ ~4~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 1~ là "()".