Dynamic Grid (Large)

You have a grid with $R$ rows and $C$ columns in which every cell holds 0 or 1. You perform $N$ operations on the grid. Each operation is one of the following two kinds.

• Operation M: change the value of one cell of the grid to 0 or 1.
• Operation Q: report the number of connected regions of 1s. A connected region of 1s is a set of cells that all hold 1, and from any cell of the set you reach every other cell of the set by moving between cells that share an edge. Two cells that touch only at a corner are not connected.

The first line holds the number of test cases $T$. Each test case starts with a line holding two integers $R$ and $C$, the number of rows and the number of columns of the grid. The next $R$ lines each hold a string of length $C$ made only of the characters 0 and 1, giving the initial state of the grid. Rows are numbered from $0$ to $R-1$ and columns from $0$ to $C-1$.

The next line holds one integer $N$, the number of operations to perform. $N$ lines follow, one operation per line. An operation M has the form M x y z and means that the cell at row $x$ and column $y$ takes the value $z$. An operation Q is the single character Q.

For each test case, first print Case #x: on its own line, where $x$ is the test case number starting from 1. Then, for every operation Q of that test case, in the order the operations are given, print the number of connected regions of 1s on its own line.

• $1 \le T \le 10$
• $1 \le R, C \le 100$
• $0 \le x < R$
• $0 \le y < C$
• $0 \le z \le 1$
• $1 \le N \le 1000$