Little Girl, Tough Game

Samiya, a little girl, wrote a random sequence of opening brackets and closing brackets on a piece of paper with the pencil and wondered if she takes a subsection of the sequence and rearranges them if it’s possible to form a valid sequence.

Some example of valid sequence of opening and closing brackets: (()), (()()), ((())()).
Some example of invalid sequence: ((()), (()))()), )()()()(()

As she is very young and playful girl, she sometimes replaces ‘(‘ with ‘)’ and vice versa from a position.
As the sequence can be very long in length, she can’t do the calculations on paper, instead, she asks you to help her.

Will you be kind enough to this little innocent girl?

Input

At first line, an integer T will be given, T test cases will follow.

For every test case, you will be given a sequence S, consisting of ‘(‘ and ‘)’. The next line, there will be an integer Q, the number of queries. Then Q query lines will follow.
The queries will be of two types.

1 i j
2 i

The first type of query asks you if it’s possible to rearrange the sequence started from i’th index, ending at j’th index such a way that it forms a valid sequence of opening and closing brackets.

The second type of query wants you to toggle the character at position i. That means if there is a ‘(‘, it’will be ‘)’, if there is ‘)’, it’ll be ‘(‘.

Output

For every case, print the case number.
For every query of type 1, print “YES” on a new line if it’s possible to form a valid sequence rearranging the sequence starting at index i, ending at index j. Otherwise print “NO” on a new line, without the quotes.

Constraints

1 <= T <= 5
1 <= |S| <= 10^5
1 <= Q <= 10^5
1 <= i <= j <= |S|

Sample

Input	Output
1 ))(( 5 1 2 3 2 2 1 2 3 2 4 1 1 4	Case 1: YES NO YES

Data set is huge, use faster IO methods.