H. Harvesting Hack
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tzuyu's first mini album, "abouTZU", is coming out on September 6th!

As a huge Tzuyu fan, Bob plans to buy the album and all related merchandise. Unfortunately, after checking his bank account balance, Bob discovers that he doesn't have enough money to fulfill his plan. He needs to earn as much as possible in the remaining days.

To begin with, Bob is going to harvest grass from his field and sell them to the market. Bob's field is a rectangular grid with $$$R$$$ rows and $$$C$$$ columns. Initially, some cells contain grass, while others do not because Bob forgot to plant grass in some areas. Note that it is possible for the field to completely fill with grass or be empty.

To make the harvesting process easier, Bob uses a special mowing machine that can harvest grass on an entire row or column for each operation. To complete the job quickly, Bob drafts a sequence of machine operations and wants to assess the efficiency of each operation. The efficiency of an operation is defined as the number of connected components formed by grass cells in the field after performing this operation. Two grass cells belong to the same connected component if they share a common edge, i.e., they are adjacent to each other horizontally or vertically.

Since the field is too large for him to count the connected components manually, Bob asks for your help. Please assist Bob by determining the number of connected components of grass cells remaining in the field after each use of the mowing machine according to his plan.

Input

The first line of the input contains two integers, $$$R$$$ and $$$C$$$ ($$$1 \leq R, C \leq 1000$$$), indicating the number of rows and columns of the grid respectively. Each of the following $$$R$$$ lines contains $$$C$$$ characters, where the $$$j^{th}$$$ character on the $$$i^{th}$$$ line represents the status of the cell in the $$$i^{th}$$$ row and $$$j^{th}$$$ column of the grid. The characters are either E indicating an empty cell or G indicating a cell with grass.

The next line contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), representing the number of operations in Bob's plan. Each of the next $$$Q$$$ lines describes a mowing machine operation in chronological order. Each operation is described by a character $$$T_i$$$ and an integer $$$K_i$$$. $$$T_i$$$ is either C indicating a column operation or R indicating a row operation, where $$$K_i$$$ represents which row or column the mowing machine is used on. Please note that rows are numbered from $$$1$$$ to $$$R$$$ and columns are numbered from $$$1$$$ to $$$C$$$.

It is guaranteed that all rows and columns the mowing machine works on exist.

Output

Output $$$Q$$$ lines, each line contains a single integer. The integer on the $$$i^{th}$$$ line represents the number of connected components formed by grass cells remaining in the field after the $$$i^{th}$$$ mowing machine operation.

Examples
Input
4 5
EGGEE
GGEEE
GEGEG
EEGGG
3
R 3
C 4
C 1
Output
2
3
3
Input
3 3
GGG
GGG
GGG
3
R 2
C 2
R 3
Output
2
4
2
Note

For Sample 2, the grid changes as the following:

  • At the beginning, every cell in the grid is filled with grass.
  • The first operation clears all grass in row 2, there are 2 connected components left in the grid.
  • The second operation clears all grass in column 2, there are 4 connected components left in the grid.
  • The third operation clears all grass in row 3, there are 2 connected components left in the grid.