Bob is doing some spring cleaning! He has a rectangular carpet which can be represented as an ~M~ by ~N~ 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 ~1~, column ~1~), 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 ~Q~ changes to the carpet of the form ~a_i\ b_i~ in which the cell in row ~a_i~, column ~b_i~ becomes reversed. After each change, can you tell Bob the minimum number of moves he needs to make his carpet pristine?

Constraints

~1 \le a_i \le M~
~1 \le b_i \le N~

Subtask 1 [20%]

~1 \le M, N \le 1\,000~
~Q = 1~

Subtask 2 [20%]

~M = 1~
~1 \le N \le 1\,000~
~1 \le Q \le 500\,000~

Subtask 3 [60%]

~1 \le M, N \le 1\,000~
~1 \le Q \le 500\,000~

Input Specification

The first line contains two space-separated integers, ~M~ and ~N~.
The next ~M~ lines each contain a string of ~N~ characters, either C or D which represents a clean or dirty cell respectively.
The following line contains a single integer, ~Q~.
The next ~Q~ lines each contain two space-separated integers, ~a_i~ and ~b_i~.

Output Specification

Output ~Q~ 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

---