Kiểm tra dãy ngoặc (Parenthesis Checking)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Cho chuỗi $S$ độ dài $N$ chỉ gồm ( và ). Có $Q$ truy vấn:

• 1 l r: hoán đổi ký tự ở vị trí $l$ và $r$.
• 2 l r: kiểm tra chuỗi con liên tiếp $S_lS_{l+1}\ldots S_r$ có phải là một dãy ngoặc đúng hay không.

Một dãy ngoặc đúng phải có tổng cân bằng cuối cùng bằng $0$ và khi quét từ trái sang phải, số ngoặc đóng chưa bao giờ vượt số ngoặc mở.

Input

Dòng đầu chứa $N,Q$.

Dòng thứ hai chứa $S$.

$Q$ dòng tiếp theo chứa truy vấn; luôn có $1\le l<r\le N$ và có ít nhất một truy vấn loại 2.

Output

Với mỗi truy vấn loại 2, in Yes nếu chuỗi con là dãy ngoặc đúng, ngược lại in No.

Subtask

• Subtask 1 — 20%: $1\le N,Q\le 50$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$.
• Subtask 3 — 50%: $1\le N,Q\le 2\cdot10^5$.

Ví dụ

Input

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

Output

Yes
No
No

Giải thích

Chuỗi con (()) là đúng, còn (( và )( đều không phải dãy ngoặc đúng.