Parenthesis Checking

Source: AtCoder

Version: Phuoc Hung OJ Extended

You are given a string $S$ of length $N$ consisting only of ( and ). Process $Q$ queries:

• 1 l r: swap the characters at positions $l$ and $r$.
• 2 l r: determine whether the contiguous substring $S_lS_{l+1}\ldots S_r$ is a correct parenthesis sequence.

A correct parenthesis sequence has total balance $0$, and while scanning left to right, its balance never becomes negative.

Input

The first line contains $N,Q$.

The second line contains $S$.

The next $Q$ lines contain queries. It is guaranteed that $1\le l<r\le N$ and at least one type 2 query exists.

Output

For every type 2 query, print Yes if the substring is correct and No otherwise.

Subtasks

• 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$.

Examples

Input

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

Output

Yes
No
No

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.