L. Kalopsia Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a bracket sequence $$$s$$$, or, in other words, a string $$$s$$$ of length $$$n$$$, consisting of characters '(' and ')', and should process $$$q$$$ number of queries. There are two types of queries:

  • $$$1$$$ $$$l$$$ $$$r$$$ : Flip the substring $$$s[l..r]$$$; in other words, for each $$$s_{i} (l \le i \le r)$$$, change '(' to ')' and vice versa.

  • $$$2$$$ $$$l$$$ $$$r$$$ : Check if the substring $$$s[l..r]$$$ is a regular bracket sequence$$$^1$$$ or not.

For example, if the string $$$s$$$ is ()(()) and the query is $$$t_i = 1, l_1 = 4, r_1 = 5$$$, then after flipping, we get the string $$$s$$$ is ()()(). If after that, we processed the query $$$t_i = 1, l_2 = 1, r_2 = 6$$$ then after flipping, the updated string $$$s$$$ will be )()()(.

$$$^1$$$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"), and ")(", "(" and ")" are not.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n,q\leq 2\cdot10^5)$$$ — the length of string $$$s$$$ and the number of queries, respectively.

The second line contains the string $$$s$$$ , consisting of $$$n$$$ characters. Each character of $$$s$$$ is either '(' or ')'.

Each of the next $$$q$$$ lines contains three integers: $$$t$$$, $$$l$$$ and $$$r$$$. $$$(1\le t_i\le 2, 1\le l_i \le r_i\le n)$$$.

Output

For each query of type $$$2$$$, print "YES" (without quotes) if the substring $$$s[l..r]$$$ is a regular bracket sequence. Print NO (without quotes) otherwise.

Example
Input
6 7
(()())
2 2 3
1 2 2
2 1 2
2 3 4
2 4 5
1 2 4
2 1 6
Output
YES
YES
NO
YES
YES