1559 - ACM

Time Limit : 2 Second

Memory Limit : 128 MB

Submission: 168

Solved: 17

Description
Jianhe25 is a ACMer, he loves "ACM" very much, so he wants to know how many times "ACM" appear in the string.

Jianhe25 thinks it's so naive, so he wants to make it more difficult. He defines two types of operation:

C i x

It means to change the ith character into x , and x is a character which will always be capital letters 'A', 'C' or 'M'.

Q i j ( 1 <=i <= j<=n )

It means to count the times the substring "ACM" appear within the range of [i,j] of the string and print it on the screen.

Input
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has two integers n m , 1 <= n,m <= 10000 , that represents the length of the string and the number of operations, and the second line contains n character which always be the Capital letters 'A','C'or'M'. Followed by m lines, each line represents the operation.

Output
The output should contain the times "ACM" appear in the string, one per line.

 

sample input
1
6 8
ACACMM
Q 1 6
Q 1 2
C 3 M
C 4 A
C 5 C
C 6 M
Q 1 6
Q 2 4
sample output
1
0
2
0
hint
Huge Input/Output , scanf/printf is recommended.
source
The 6th ACM Programming Contest of HUST
© 2015 HUST ACMICPC TEAM. All Right Reserved.