## Another Random Contest 1 P4 - Bracket Query

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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

• An empty sequence is valid.
• If is a valid bracket sequence, then () is a valid bracket sequence.
• If and are valid bracket sequences, then the concatenation of and , , 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 . The professor will ask you queries, each consisting of two numbers, and . For each query, you need to check if it is possible to insert a continuous number (possibly zero) of ( or ) brackets into the interval to 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.

#### Input Specification

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

The next line consists of a bracket sequence of length .

The following lines consist of two integers, and .

#### Output Specification

Output YES and NO on 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