Cho một xâu độ dài ~N~ chỉ gồm các kí tự '(' và ')', các kí tự được đánh số từ ~1~ đến ~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à ~1~ dãy ngoặc đúng.
• Nếu ~A~ là ~1~ dãy ngoặc đúng thì ~(A)~ là ~1~ dãy ngoặc đúng.
• Nếu ~A~ và ~B~ là ~2~ dãy ngoặc đúng thì ~AB~ là ~1~ dãy ngoặc đúng.

Cho ~M~ truy vấn, mỗi truy vấn thuộc ~1~ trong ~2~ loại sau:

• ~0~ ~i~ ~ch~: thay đổi kí tự ở vị trí ~i~ của xâu kí tự thành kí tự ~ch~.
• ~1~ ~i~ ~j~: in ra ~1~ nếu xâu con từ vị trí ~i~ đến vị trí ~j~ là một dãy ngoặc đúng, in ra ~0~ trong trường hợp ngược lại.

Input

• Dòng đầu tiên chứa ~2~ số ~N~, ~M~
• Dòng tiếp theo chứa ~N~ kí tự liên tiếp.
• ~M~ dòng tiếp theo, mỗi dòng chứa ~1~ truy vấn thuộc ~1~ trong ~2~ loại trên.

Output

In ra ~0~ hoặc ~1~ tương ứng với mỗi truy vấn loại ~2~.

Giới hạn

~2 \le N \le 100000~

~1 \le M \le 200000~

Trong truy vấn loại ~1~: ~1 \le i \le N~; ch là '(' hoặc ')'

Trong truy vấn loại ~2~: ~1 \le i \le j \le N~;

Sample Input

8 7
()))(())
1 1 2
1 3 4
0 3 (
1 1 4
1 5 8
0 6 )
1 5 8

Sample Output

10110