z-blocks
Little Z has a bunch of block ordered in a row. Each block is colored either in black or white color. Tomorrow, his friend will come to visit him and they will play next game:
Little Z will close his eyes and his friend will start swaping sub-rows of blocks. When they ask him how many blocks are colored in black in some sub-row he should tell them.
Please, help to Little Z and write program that give answers, so he could always know correct answer.
InputThe first line of the standard input contains two space-separated cardinals N, (1 <= N <= 20 000), representing number of blocks and Q (1 <= Q <= 200 000), representing number of operations. In the next line you will be given string of the length N consisted of upper-case letters 'B' and 'W' ('B' stands for black, 'W' stands for white), where i-th character represents color of i-th block. Next Q lines will contain operations.
Possible operations are:
S pos1 pos2 length - means that blocks at positions (pos1, pos1 + 1, ..., pos1 + length - 1) should be swaped with blocks at positions (pos2, pos2 + 1, ..., pos2 + length - 1). 1 <= pos1, pos2 <= N; 1 <= length <= 800; pos1 + length - 1, pos2 + length - 1 <= N. Blocks that should be swaped in one operation will never overlap.
C pos1 pos2 - print how many blocks colored in black are at positions from interval [ pos1, pos2 ]. 1 <= pos1 <= pos2 <= N; pos2 - pos1 + 1 <= 800.
Possible operations are:
S pos1 pos2 length - means that blocks at positions (pos1, pos1 + 1, ..., pos1 + length - 1) should be swaped with blocks at positions (pos2, pos2 + 1, ..., pos2 + length - 1). 1 <= pos1, pos2 <= N; 1 <= length <= 800; pos1 + length - 1, pos2 + length - 1 <= N. Blocks that should be swaped in one operation will never overlap.
C pos1 pos2 - print how many blocks colored in black are at positions from interval [ pos1, pos2 ]. 1 <= pos1 <= pos2 <= N; pos2 - pos1 + 1 <= 800.
OutputOn the standard output for each C operation print the answer in order they appear in the input. Each answer should be printed in a new line.
Input:
Output:
8 5
BBWBWBWW
C 5 8
S 1 6 2
C 5 8
S 1 5 4
C 1 4Output:
1
2
2Explanation:
1. colors of blocks in interval [5, 8] are white, black, white, white (in that order), so there is 1 black block.
2. swapping 1st and 2nd block with 6th and 7th, consecutively, gives BWWBWBBW
3. number of black blocks in interval [5, 8] is 2 - note that now colors of blocks are BWWBWBBW
4. swapping [1, 4] with [5, 8] gives WBBWBWWB
5. number of black blocks in interval [1, 4] is 2 - 2nd and 3rd block.
Input:
Output:
12 8
BBWBWWBWBBBW
C 1 12
S 1 6 5
S 8 2 3
C 4 12
S 12 11 1
C 10 12
C 3 6
C 2 9Output:
7
6
2
3
5Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.