{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAlex is a professional computer game player.\u003c/p\u003e\u003cp\u003eThese 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.\u003c/p\u003e\u003cp\u003eThe 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\u003d1$$$ or $$$b\u003d1$$$ is also allowed. Each cell has a state, wet or dry. It is impossible to build a bounding wall across a wet cell.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/e9db1e14d4bd8c4a0b865b607f0abc36?v\u003d1715817342\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eHe will also have several queries about building a bounding wall. The only two possible formats about queries are listed as follows.\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e1 x y\u003c/span\u003e : the state of cell $$$(x,y)$$$ changes. \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e2 x y\u003c/span\u003e : 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. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input gives the number of test cases, $$$T\\ (1 \\le T \\le 1000)$$$. $$$T$$$ test cases follow.\u003c/p\u003e\u003cp\u003eFor 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.\u003c/p\u003e\u003cp\u003eEach of the following $$$n$$$ lines contains a string $$$s_{i,1}s_{i,2}\\cdots s_{i,m}\\ (s_{i,j} \u003d $$$\u003cspan class\u003d\"tex-font-style-tt\"\u003e\u0027#\u0027 or \u0027.\u0027\u003c/span\u003e$$$)$$$, describing the initial state of his land. If $$$s_{x,y} \u003d $$$\u003cspan class\u003d\"tex-font-style-tt\"\u003e\u0027#\u0027\u003c/span\u003e, the cell $$$(x,y)$$$ will be dry, otherwise, it will be wet.\u003c/p\u003e\u003cp\u003eEach 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.\u003c/p\u003e\u003cp\u003eThe sum of $$$\\max\\{n,m,Q\\}$$$ in all test cases doesn\u0027t exceed $$$2 \\times 10^4$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, the output starts with a line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x:\u003c/span\u003e\", where $$$\\texttt{x}$$$ is the test case number (starting from $$$1$$$). For each queries with $$$t_i \u003d 2$$$, answer the maximum possible coverage area. If it is impossible to build a bounding wall, print $$$0$$$.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 3 2\n###\n##.\n2 2 2\n2 1 3\n4 3 3\n###\n#.#\n#.#\n###\n2 3 2\n1 3 2\n2 3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\n4\n3\nCase #2:\n0\n9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}