提示: 欢迎访问OurACM平台。
Problem 1978 Repair the brackets

Accept: 75    Submit: 303
Time Limit: 2000 mSec    Memory Limit : 32768 KB

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

Submit  Back  Status  Discuss