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 1000$
$Q=1$

Subtask 2 [20%]

$M=1$
$1\le N\le 1000$
$1\le Q\le 500000$

Subtask 3 [60%]

$1\le M,N\le 1000$
$1\le Q\le 500000$

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