Description

小叶子早早的来到了盐星船站，发现要等好久才轮到自己。
盐星船站是一个n*m的矩形（左上角坐标为（1,1），右下角坐标为（n,m）），对于矩阵上每个位置a[i,j]，如果a[i,j]为1表示该位置停着一艘飞船等待起飞，为0表示空着。
盐星船站有一个很奇怪的规矩，如果在a[i,j]位置的飞船要出发，则以a[i,j]为边界的最大面积的子矩形内的所有飞船都要起飞。也就是说对于满足要求的一个子矩形（左上角坐标为（x1,y1），右下角坐标为（x2，y2））,有条件如下：
    ((i = x1 || i = x2) && (y1 <= j <= y2)) || ((j = y1 || j = y2) && (x1 <= i <= x2))
且该子矩阵内所有位置都要停着飞船（如果这种子矩阵不止一个，则是任意的一个）。

Input

输入有多组测试数据
第一行三个数字，n，m，q（1<=n,m,q<=1000)
接下来n行输入由0,1构成的n*m矩阵，代表停船场初始状态
接下来q行，每行三个数op,i,j
op = 1 如果a[i,j]=1表示（i,j）位置的飞船被拖走修整，如果a[i,j]=0表示有一艘飞船修整完毕，停回（i,j）等待起飞
op = 2 表示(i,j)位置的飞船正要起飞

Output

对于每个op=2的操作输出有多少飞船需要起飞

Sample Input

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

3 3 4
1 1 1
1 1 1
1 1 1
2 2 2
1 2 2
2 1 1
2 2 1

Sample Output

0
2
6
6
3
3

HINT

op=2,飞船只是打算起飞，没有真的飞走

Source

Codeforces