Problem Statement

Takahashi is investigating the relationship between buildings and roads in a certain city.

The city is represented as a grid with H rows and W columns. The cell at the i-th row from the top (1 \leq i \leq H) and the j-th column from the left (1 \leq j \leq W) is denoted as (i, j). Each cell has one of the following types:

• B : Building
• R : Road
• E : Empty lot

In the initial state, the type of cell (i, j) is given by the j-th character of the string S_i.

A building cell is said to be facing a road if at least one of its vertically or horizontally adjacent cells is a road cell. Diagonally adjacent cells are not considered as facing a road.

From now on, Q road construction operations will be performed in order. The effects of construction are cumulative (once a cell becomes a road, it remains a road throughout all subsequent operations).

In the k-th operation (1 \leq k \leq Q), all empty lot cells within the rectangular region from row U_k to row D_k and from column L_k to column R_k are converted to road cells. Cells that are already roads or buildings do not change. Cells outside the construction area also do not change.

It is guaranteed that no building cells are contained within the rectangular region of each construction operation.

After each construction operation, determine the total number of building cells that are facing a road. Even if a single building cell is adjacent to multiple road cells, it is counted as one.

Constraints

• 1 \leq H, W \leq 10^6
• 1 \leq Q \leq 10^5
• H W \leq 2 \times 10^6
• H + Q \leq 2 \times 10^5
• S_i (1 \leq i \leq H) is a string of length W, where each character is one of B, R, or E
• 1 \leq U_k \leq D_k \leq H (1 \leq k \leq Q)
• 1 \leq L_k \leq R_k \leq W (1 \leq k \leq Q)
• \displaystyle \sum_{k=1}^{Q} \left( 2(D_k-U_k+1) + 2(R_k-L_k+1) \right) \leq 5 \times 10^6
• No cell with B is contained within the rectangular region of each construction operation
• All inputs are integers and strings

Sample Input 1

4 5 3
EEEEE
EBERE
EEEEE
REBEE
1 1 1 3
3 4 4 5
2 3 3 3

Sample Output 1

1
2
2

Sample Input 2

3 3 4
BEB
EEE
BEB
2 2 2 2
1 3 2 2
2 2 1 3
1 1 2 2

Sample Output 2

0
4
4
4

Sample Input 3

8 10 7
EEREEEEEER
EEBEEEEEEE
EEEEERBEEE
EEEEEEEEEE
BEEEEEEEER
EEEEREEEEE
EEEEBEEEEE
REEEEEEEEE
1 1 1 5
4 4 1 10
2 3 4 6
5 6 2 4
6 8 6 8
1 3 8 10
7 8 1 3

Sample Output 3

3
4
4
4
4
4
4

Sample Input 4

12 15 10
EEEEREEEEEEEEEE
EEEEBEEEREEBEEE
EEEEEEEEEEEEEEE
EEBEEEEEEEEEEER
EREEEEEEEBEEEEE
EEEEEEEEEEEEERE
EEEEEEBEEEEEEBE
EEEEEEEEEEEEEEE
BEEEEEEBEEEEEER
EEEEREEEEEEEEEE
EEEBEEEEEEBEEEE
REEEEEEEEEEEEER
1 1 1 15
2 8 1 1
3 6 4 8
2 4 13 15
5 6 11 15
8 10 2 4
10 12 12 15
6 8 8 13
3 3 1 15
12 12 1 15

Sample Output 4

3
4
6
6
7
8
9
10
10
10

Sample Input 5

1 1 1
E
1 1 1 1

Sample Output 5

0