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