407343: GYM102769 B Bounding Wall

Alex is a professional computer game player.

These days, Alex is playing a war strategy game. His land is a rectangular grid with $$$n$$$ rows by $$$m$$$ columns of cells. He wants to build a bounding wall to protect some vital materials.

The bounding wall is a frame of $$$a \times b$$$ rectangle whose width is $$$1$$$. It occupies $$$a$$$ rows and $$$b$$$ columns, and its coverage area is $$$a\cdot b$$$. Note that $$$a=1$$$ or $$$b=1$$$ is also allowed. Each cell has a state, wet or dry. It is impossible to build a bounding wall across a wet cell.

He will also have several queries about building a bounding wall. The only two possible formats about queries are listed as follows.

• 1 x y : the state of cell $$$(x,y)$$$ changes.
• 2 x y : Alex wants to build a bounding wall across the cell $$$(x,y)$$$ such that the coverage area is as large as possible. Answer the maximum coverage area.

The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 1000)$$$. $$$T$$$ test cases follow.

For each test case, the first line contains three integers $$$n,m$$$ and $$$Q\ (1 \le n,m,Q \le 10^3)$$$, representing his land has $$$n$$$ rows and $$$m$$$ columns, and he will have $$$Q$$$ queries.

Each of the following $$$n$$$ lines contains a string $$$s_{i,1}s_{i,2}\cdots s_{i,m}\ (s_{i,j} = $$$'#' or '.'$$$)$$$, describing the initial state of his land. If $$$s_{x,y} = $$$'#', the cell $$$(x,y)$$$ will be dry, otherwise, it will be wet.

Each of the following $$$Q$$$ lines contains three integers $$$t_i\ (1 \le t_i \le 2)$$$, $$$x_i\ (1 \le x_i \le n)$$$ and $$$y_i\ (1 \le y_i \le m)$$$, representing a query.

The sum of $$$\max\{n,m,Q\}$$$ in all test cases doesn't exceed $$$2 \times 10^4$$$.

For each test case, the output starts with a line containing "Case #x:", where $$$\texttt{x}$$$ is the test case number (starting from $$$1$$$). For each queries with $$$t_i = 2$$$, answer the maximum possible coverage area. If it is impossible to build a bounding wall, print $$$0$$$.

2
2 3 2
###
##.
2 2 2
2 1 3
4 3 3
###
#.#
#.#
###
2 3 2
1 3 2
2 3 2

Case #1:
4
3
Case #2:
0
9