A valid bracket sequence consisting of ( and ) is defined as follows:

• An empty sequence is valid.
• If $X$ is a valid bracket sequence, then ($X$) is a valid bracket sequence.
• If $X$ and $Y$ are valid bracket sequences, then the concatenation of $X$ and $Y$, $Z=X+Y$, is a valid bracket sequence.

For example, (()), ()(), and (()())() are all valid bracket sequences, while ( and ()) are invalid bracket sequences.

A professor gave you a sequence of brackets of length $N$. The professor will ask you $Q$ queries, each consisting of two numbers, $l_i$ and $r_i$. For each query, you need to check if it is possible to insert a continuous number (possibly zero) of ( or ) brackets into the interval $l_i$ to $r_i$ to make the subsequence valid.

For example:

Let the original string be xxxxxxx.

Then, xxxxx((((((xx or xxxxxxx))))) are all valid insertions.

If it is possible, output YES; otherwise, output NO.

Constraints

For all subtasks:

$1\le N,Q\le 2\times {10}^5$

$1\le l_i\le r_i\le N$

Subtask 1 [20%]

$1\le N,Q\le 5\times {10}^3$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line consists of two integers $N$ and $Q$, the length of the string and the number of queries.

The next line consists of a bracket sequence of length $N$.

The following $Q$ lines consist of two integers, $l_i$ and $r_i$.

Output Specification

Output YES and NO on $Q$ separate lines, each line answering a query.

Sample Input

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

Sample Output

YES
NO
NO
NO
YES
YES
YES
NO