H. Rebellious Sequences
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A bracket sequence is a sequence of opening and closing brackets. A bracket sequence is called balanced if and only if two conditions hold:

  • it contains equal number of opening and closing brackets;
  • for each prefix, the number of closing brackets is not greater than the number of opening brackets.

A bracket sequence is called rebellious if it contains equal number of opening and closing brackets and is not balanced.

You are given a balanced bracket sequence of $$$n$$$ brackets and $$$q$$$ queries to it. Each query asks you to swap two brackets. It is guaranteed that after each query the sequence stays balanced.

After each query you should find whether it is possible to split the sequence into several disjoint rebellious subsequences.

Formally, let the original sequence be $$$s_1s_2 \dots s_n$$$. You have to check if there exists a number $$$k \gt 1$$$ (the number of subsequences) and $$$k$$$ non-empty sequences of indices $$$(i_{1, 1} \lt \ldots \lt i_{1, l_1}), \dots, (i_{k, 1} \lt \ldots \lt i_{k, l_k})$$$ such that for each $$$1 \leq j \leq k$$$ the bracket sequence $$$s_{i_{j, 1}} s_{i_{j, 2}} \dots s_{i_{j,l_{j}}}$$$ is rebellious and every integer from $$$1$$$ to $$$n$$$ appears among those sequences exactly once.

Input

The first line of the input contains two numbers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 300\ 000$$$), the length of the sequence and the number of queries respectively. In the second line, there is a string of length $$$n$$$ consisting of characters '(' and ')'.

Then follow $$$q$$$ lines that describe the queries. Each of them contains two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i \lt j \leq n$$$), denoting that you should swap the brackets on $$$i$$$-th and $$$j$$$-th position.

It is guaranteed that the sequence is balanced initially and remains balanced after each query.

Output

After each query print "Yes", if it is possible to split the sequence into several disjoint rebellious subsequences, and "No" otherwise.

Example
Input
8 4
(()()())
3 4
5 6
2 7
6 7
Output
No
No
Yes
No