Bob is doing some spring cleaning! He has a rectangular carpet which can be represented as an by grid of cells. Each cell is either dirty or clean. Bob can clean this grid by choosing a subrectangle which contains the top-left cell (in row , column ), and reversing the states of all the cells in this subrectangle. This constitutes a single move. He wants to clean the carpet in as few moves as possible. In addition, the carpet changes sometimes. There are changes to the carpet of the form in which the cell in row , column becomes reversed. After each change, can you tell Bob the minimum number of moves he needs to make his carpet pristine?
Constraints
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [60%]
Input Specification
The first line contains two space-separated integers, and .
The next lines each contain a string of characters, either C
or D
which represents a clean or dirty cell respectively.
The following line contains a single integer, .
The next lines each contain two space-separated integers, and .
Output Specification
Output lines. Each line should contain a single integer, the answer after each change.
Sample Input 1
3 4
CCCC
CCCC
CCCC
3
1 1
2 1
1 2
Sample Output 1
1
1
3
Explanation for Sample 1
The carpet after each change is:
DCCC DCCC DDCC
CCCC DCCC DCCC
CCCC CCCC CCCC
Then to clean the third carpet, for example, Bob first chooses the subrectangle from (1, 2):
CCCC
DCCC
CCCC
Next he chooses the subrectangle from (2, 1):
DCCC
CCCC
CCCC
Finally, he chooses the subrectangle from (1, 1):
CCCC
CCCC
CCCC
which gives three moves.
Sample Input 2
3 3
CCC
CDC
CCC
3
2 1
2 1
2 2
Sample Output 2
2
4
0
Comments