A valid bracket sequence consisting of
) 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.
(()())() are all valid bracket sequences, while
()) 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
) brackets into the interval to to make the subsequence valid.
Let the original string be
xxxxxxx))))) are all valid insertions.
If it is possible, output
YES; otherwise, output
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
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 .
NO on separate lines, each line answering a query.
8 8 (())()(( 5 6 2 7 6 7 4 5 5 7 7 8 3 4 6 7
YES NO NO NO YES YES YES NO