七海是玩游戏的专家。这天,七海的好朋友阿一邀请她去看棒球比赛。她虽然不甘心,但还是跟着他去了体育场。不过七海对这个游戏没什么兴趣,所以她环顾四周,看看有没有什么能让她感兴趣的东西。就在那时,她看到了体育场一端的数字板。
数字板的高度为 n 个像素,宽度为 m 个像素,每个像素要么亮,要么暗。像素由其坐标来描述。第i行的第j个像素是像素(i,j)。该板通过将像素组合切换为亮,将其余像素切换为暗来显示消息。七海注意到板上像素的状态会不时发生变化。在某些时候,板上的某些像素可能会从亮变为暗,或从暗变为亮。
Nanami 想知道,特定像素位于其一侧的最大光块的面积是多少。光块是板的子矩形,其中所有像素都是光的。像素(i,j)属于以(x1,y1)和(x2,y2)为左上和右下顶点的子矩形的一条边当且仅当它满足逻辑条件:
((i = x1 或 i = x2) 和 (y1 ≤ j ≤ y2)) 或 ((j = y1 或 j = y2) 和 (x1 ≤ i ≤ x2))。
Nanami拥有更改像素的所有历史,她也有一些所描述类型的问题,你能回答吗?
输入
第一行包含三个空格分隔的整数 n、m 和 q (1 ≤ n, m, q ≤ 1000) — 数字板的高度和宽度以及操作次数。
接下来是 n 行,每行包含 m 个空格分隔的整数。第 i 行的第 j 个整数是 ai, j — 像素 (i, j) 的初始状态。
- 如果 ai, j = 0,则像素 (i, j) 最初是暗的。
- 如果 ai, j = 1,则像素 (i, j) 最初是亮的。
然后是 q 行,每行包含三个空格分隔的整数 op、x 和 y (1 ≤ op ≤ 2; 1 ≤ x ≤ n; 1 ≤ y ≤ m),描述一个操作。
- 如果 op = 1,则 (x, y) 处的像素改变其状态(从亮到暗或从暗到亮)。
- 如果 op = 2,Nanami 查询其一侧有像素 (x, y) 的最大光块。
输出
对于每个查询,打印一行包含一个整数 - Nanami 查询的答案。
示例
输入 #1
3 4 5 0 1 1 0 1 0 0 1 0 1 1 0 2 2 2 2 1 2 1 2 2 1 2 3 2 2 2
输出 #1
0 2 6
输入 #2
3 3 4 1 1 1 1 1 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 1
输出 #2
6 3 3
注意
考虑第一个样本。
第一个查询指定像素 (2, 2),该像素本身是暗的,因此没有有效的光块,因此答案为 0。
第二个查询指定像素 (1, 2)。最大的光块是左上顶点为 (1, 2) 、右下顶点为 (1, 3) 的块。
最后一个查询指定像素 (2, 2),该像素在第三次操作中变亮。最大的光块是左上顶点为 (1, 2) 、右下顶点为 (3, 3) 的块。