## Problem Description

A regular bracket sequence is defined as follows:

1. Empty sequence is a regular bracket sequence.
2. If S is a regular bracket sequence, then (S) is also a regular bracket sequence.
3. If a and b are regular bracket sequences, then ab is a regular bracket sequence.
4. Any other sequences are not regular bracket sequences.

Given a bracket sequence S of size N consisting of '(' and ')'. Each time you should simulate one of the following operations:

1. Replace f r c: Replace all brackets by c in [f, r].
2. Swap f r: Reverse all brackets in [f, r].
3. Invert f r: Invert all brackets in [f, r] from '(' to ')' and vice versa.
4. Query f r: Output the minimum changes to repair the brackets in [f, r] into
a regular bracket sequence. To repair the brackets each time you can invert a
bracket from '(' to ')' or vice versa. For example, you need 2 changes to
repair "((((" to "(())" by inverting the last two '(' to ')'. The length of
the query sequence, that is r-f+1, will always be even.
**You should note that f and r will fit 1≤f≤r≤N, c is either '(' or ')'.**

## Input

In the first line there is an integer T (T≤50), indicates the number of test cases. Each case begins with a line containing two integers N (1≤N≤50,000) and M (1≤M≤50,000), the size of the initial brackets sequence and the number of queries. The next line contains N characters consisting of '(' and ')'. Each of the following M lines contains one operation as said above. The index of the bracket sequence is labeled from 1 to N.

## Output

For each test case, print a line containing the test case number (beginning with 1) on its own line, then the minimum changes to repair the brackets in [f, r] into a regular brackets sequence for each "Query" operation, one on each line.

## Sample Input

4
2 2
((
Invert 1 2
Query 1 2
3 1
(()
Invert 1 3
8 4
)))()()(
Invert 6 7
Swap 3 6
Replace 5 7 (
Query 4 7
9 3
(())()(()
Swap 1 7
Replace 8 9 (
Query 1 4

## Sample Output

Case 1:
1
Case 2:
Case 3:
3
Case 4:
0

## Source

The 35th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest