Dynamic Grid (Small)

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

• Operation M: change one cell of the grid to 0 or 1.
• Operation Q: count the connected regions of 1s. A connected region of 1s is a maximal set of cells that all hold 1 such that you can walk from any cell of the set to any other cell of the set by moving only 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$. $T$ test cases follow.

Each test case starts with a line holding two integers $R$ and $C$, the number of rows and the number of columns. The next $R$ lines each hold a string of $C$ characters that are 0 or 1, and these lines are the initial grid. Rows are numbered from 0 at the top, columns from 0 at the left.

The next line holds one integer $N$, the number of operations. The next $N$ lines each hold one operation. An M operation is written M x y z and sets the cell in row $x$ and column $y$ to $z$. A Q operation is written Q.

For each test case, first print one line holding Case #x:, where $x$ is the test case number starting from 1. Then, for every Q operation of that test case, in order, print one line holding the number of connected regions of 1s. A test case with no Q operation prints only its Case #x: 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 10$