#include<bits/stdc++.h>
using namespace std;
//#define debug(...) printf( __VA_ARGS__ )
#define debug(...) /****nothing****/
#define pb push_back
#define mp make_pair
#define LL long long
#define resett(arr,val,N) for(int ii=0;ii<(N);ii++) arr[ii]=val;
int tc,n,m,q,cnt,ar[100000],presum[100000],mxsum[100000];
int grid[600][600],ans;
void fun(int r1,int r2,int c1,int c2,int sum)
{
if(r1>r2 || c1>c2)
{
debug("\n");
return;
}
for(int i=c1; i<=c2; i++)
{
sum+=grid[r1][i];
ar[cnt]=grid[r1][i];
presum[cnt]=sum;
if(sum>ans)
ans=sum;
if(sum<0)
sum=0;
mxsum[cnt]=ans;
grid[r1][i]=cnt++;
debug("%d\t",grid[r1][i]);
}
for(int i=r1+1; i<=r2-1; i++)
{
sum+=grid[i][c2];
ar[cnt]=grid[i][c2];
presum[cnt]=sum;
if(sum>ans)
ans=sum;
if(sum<0)
sum=0;
mxsum[cnt]=ans;
grid[i][c2]=cnt++;
debug("%d\t",grid[i][c2]);
}
if(r1!=r2)
for(int i=c2; i>=c1; i--)
{
sum+=grid[r2][i];
ar[cnt]=grid[r2][i];
presum[cnt]=sum;
if(sum>ans)
ans=sum;
if(sum<0)
sum=0;
mxsum[cnt]=ans;
grid[r2][i]=cnt++;
debug("%d\t",grid[r2][i]);
}
if(c2!=c1)
for(int i=r2-1; i>=r1+1; i--)
{
sum+=grid[i][c1];
ar[cnt]=grid[i][c1];
presum[cnt]=sum;
if(sum>ans)
ans=sum;
if(sum<0)
sum=0;
mxsum[cnt]=ans;
grid[i][c1]=cnt++;
debug("%d\t",grid[i][c1]);
}
fun(r1+1,r2-1,c1+1,c2-1,sum);
}
int main()
{
cin>>tc;
for(int cas=1; cas<=tc; cas++)
{
scanf("%d %d %d",&n,&m,&q);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d",&grid[i][j]);
cnt=ans=0;
fun(1,n,1,m,0);
for(int i=0;i<cnt;i++)
debug("%d ",ar[i]);
debug("\n");
printf("Case %d:\n",cas);
int ager_query=-1,ager_ans=-1;
while(q--)
{
int ty,r,c,val;
scanf("%d",&ty);
if(ty==1)
printf("%d\n",mxsum[cnt-1]);
else
{
scanf("%d %d %d",&r,&c,&val);
ar[grid[r][c]]=val;
for(int i=grid[r][c];i<cnt;i++)
{
presum[i]=presum[i-1]+ar[i];
mxsum[i]=max(mxsum[i-1],presum[i]);
if(presum[i]<0)
presum[i]=0;
}
}
ager_query=ty;
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKLy8jZGVmaW5lIGRlYnVnKC4uLikgICBwcmludGYoIF9fVkFfQVJHU19fICkKI2RlZmluZSBkZWJ1ZyguLi4pICAgLyoqKipub3RoaW5nKioqKi8KI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBMTCBsb25nIGxvbmcKI2RlZmluZSByZXNldHQoYXJyLHZhbCxOKSBmb3IoaW50IGlpPTA7aWk8KE4pO2lpKyspIGFycltpaV09dmFsOwppbnQgdGMsbixtLHEsY250LGFyWzEwMDAwMF0scHJlc3VtWzEwMDAwMF0sbXhzdW1bMTAwMDAwXTsKaW50IGdyaWRbNjAwXVs2MDBdLGFuczsKCnZvaWQgZnVuKGludCByMSxpbnQgcjIsaW50IGMxLGludCBjMixpbnQgc3VtKQp7CiAgICBpZihyMT5yMiB8fCBjMT5jMikKICAgIHsKICAgICAgICBkZWJ1ZygiXG4iKTsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgZm9yKGludCBpPWMxOyBpPD1jMjsgaSsrKQogICAgewogICAgICAgIHN1bSs9Z3JpZFtyMV1baV07CiAgICAgICAgYXJbY250XT1ncmlkW3IxXVtpXTsKICAgICAgICBwcmVzdW1bY250XT1zdW07CgogICAgICAgIGlmKHN1bT5hbnMpCiAgICAgICAgICAgIGFucz1zdW07CiAgICAgICAgaWYoc3VtPDApCiAgICAgICAgICAgIHN1bT0wOwoKICAgICAgICBteHN1bVtjbnRdPWFuczsKICAgICAgICBncmlkW3IxXVtpXT1jbnQrKzsKCiAgICAgICAgZGVidWcoIiVkXHQiLGdyaWRbcjFdW2ldKTsKCiAgICB9CgogICAgZm9yKGludCBpPXIxKzE7IGk8PXIyLTE7IGkrKykKICAgIHsKICAgICAgICBzdW0rPWdyaWRbaV1bYzJdOwogICAgICAgIGFyW2NudF09Z3JpZFtpXVtjMl07CiAgICAgICAgcHJlc3VtW2NudF09c3VtOwoKICAgICAgICBpZihzdW0+YW5zKQogICAgICAgICAgICBhbnM9c3VtOwogICAgICAgIGlmKHN1bTwwKQogICAgICAgICAgICBzdW09MDsKCiAgICAgICAgbXhzdW1bY250XT1hbnM7CiAgICAgICAgZ3JpZFtpXVtjMl09Y250Kys7CgogICAgICAgIGRlYnVnKCIlZFx0IixncmlkW2ldW2MyXSk7CgogICAgfQoKICAgIGlmKHIxIT1yMikKICAgIGZvcihpbnQgaT1jMjsgaT49YzE7IGktLSkKICAgIHsKICAgICAgICBzdW0rPWdyaWRbcjJdW2ldOwogICAgICAgIGFyW2NudF09Z3JpZFtyMl1baV07CiAgICAgICAgcHJlc3VtW2NudF09c3VtOwoKICAgICAgICBpZihzdW0+YW5zKQogICAgICAgICAgICBhbnM9c3VtOwogICAgICAgIGlmKHN1bTwwKQogICAgICAgICAgICBzdW09MDsKCiAgICAgICAgbXhzdW1bY250XT1hbnM7CiAgICAgICAgZ3JpZFtyMl1baV09Y250Kys7CgogICAgICAgIGRlYnVnKCIlZFx0IixncmlkW3IyXVtpXSk7CgogICAgfQoKICAgIGlmKGMyIT1jMSkKICAgIGZvcihpbnQgaT1yMi0xOyBpPj1yMSsxOyBpLS0pCiAgICB7CiAgICAgICAgc3VtKz1ncmlkW2ldW2MxXTsKICAgICAgICBhcltjbnRdPWdyaWRbaV1bYzFdOwogICAgICAgIHByZXN1bVtjbnRdPXN1bTsKCiAgICAgICAgaWYoc3VtPmFucykKICAgICAgICAgICAgYW5zPXN1bTsKICAgICAgICBpZihzdW08MCkKICAgICAgICAgICAgc3VtPTA7CgogICAgICAgIG14c3VtW2NudF09YW5zOwogICAgICAgIGdyaWRbaV1bYzFdPWNudCsrOwoKICAgICAgICBkZWJ1ZygiJWRcdCIsZ3JpZFtpXVtjMV0pOwogICAgfQoKCiAgICBmdW4ocjErMSxyMi0xLGMxKzEsYzItMSxzdW0pOwp9CgppbnQgbWFpbigpCnsKICAgIGNpbj4+dGM7CiAgICBmb3IoaW50IGNhcz0xOyBjYXM8PXRjOyBjYXMrKykKICAgIHsKICAgICAgICBzY2FuZigiJWQgJWQgJWQiLCZuLCZtLCZxKTsKCiAgICAgICAgZm9yKGludCBpPTE7IGk8PW47IGkrKykKICAgICAgICAgICAgZm9yKGludCBqPTE7IGo8PW07IGorKykKICAgICAgICAgICAgICAgIHNjYW5mKCIlZCIsJmdyaWRbaV1bal0pOwoKICAgICAgICBjbnQ9YW5zPTA7CiAgICAgICAgZnVuKDEsbiwxLG0sMCk7CgogICAgICAgIGZvcihpbnQgaT0wO2k8Y250O2krKykKICAgICAgICAgICAgZGVidWcoIiVkICIsYXJbaV0pOwogICAgICAgIGRlYnVnKCJcbiIpOwoKCiAgICAgICAgcHJpbnRmKCJDYXNlICVkOlxuIixjYXMpOwoKICAgICAgICBpbnQgYWdlcl9xdWVyeT0tMSxhZ2VyX2Fucz0tMTsKCiAgICAgICAgd2hpbGUocS0tKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHR5LHIsYyx2YWw7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsJnR5KTsKICAgICAgICAgICAgaWYodHk9PTEpCiAgICAgICAgICAgICBwcmludGYoIiVkXG4iLG14c3VtW2NudC0xXSk7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc2NhbmYoIiVkICVkICVkIiwmciwmYywmdmFsKTsKICAgICAgICAgICAgICAgIGFyW2dyaWRbcl1bY11dPXZhbDsKICAgICAgICAgICAgICAgIGZvcihpbnQgaT1ncmlkW3JdW2NdO2k8Y250O2krKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBwcmVzdW1baV09cHJlc3VtW2ktMV0rYXJbaV07CiAgICAgICAgICAgICAgICAgICAgbXhzdW1baV09bWF4KG14c3VtW2ktMV0scHJlc3VtW2ldKTsKICAgICAgICAgICAgICAgICAgICBpZihwcmVzdW1baV08MCkKICAgICAgICAgICAgICAgICAgICAgICAgcHJlc3VtW2ldPTA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGFnZXJfcXVlcnk9dHk7CiAgICAgICAgfQoKCiAgICB9CgoKCiAgICByZXR1cm4gMDsKfQo=