# 2. 题解

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
#define mkp make_pair
using namespace std;
typedef pair<int,int> pii;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c=getchar();int f=1;dig=0;
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
dig*=f;
}
int t,n,m;
struct N2{int l,r,min,max;};
struct N1{int l,r;N2 d[3205];}e[3205];
void update(int a,int b)
{
e[a].d[b].max=max(e[a].d[LS(b)].max,e[a].d[RS(b)].max);
e[a].d[b].min=min(e[a].d[LS(b)].min,e[a].d[RS(b)].min);
}
void build2(int l,int r,int a,int b)
{
N2&k=e[a].d[b];
k.l=l,k.r=r,k.max=INT_MIN,k.min=INT_MAX;
if(l==r)return;
build2(l,(l+r)>>1,a,LS(b)),build2(((l+r)>>1)+1,r,a,RS(b));
}
void build1(int l,int r,int a)
{
e[a].l=l,e[a].r=r;
build2(1,n,a,1);
if(l==r)return;
build1(l,(l+r)>>1,LS(a)),build1(((l+r)>>1)+1,r,RS(a));
}
void change2(int x,int a,int b)
{
if(e[a].l==e[a].r)return;
e[a].d[b].max=max(e[LS(a)].d[b].max,e[RS(a)].d[b].max);
e[a].d[b].min=min(e[LS(a)].d[b].min,e[RS(a)].d[b].min);
if(e[a].d[b].l==e[a].d[b].r)return;
if(x<=((e[a].d[b].l+e[a].d[b].r)>>1))change2(x,a,LS(b));
else change2(x,a,RS(b));
}
void change(int x,int y,int k,int a)
{
if(e[a].l==e[a].r)
{
int i=1;
while(e[a].d[i].l!=e[a].d[i].r)
if(x<=((e[a].d[i].l+e[a].d[i].r)>>1))i=LS(i);
else i=RS(i);
e[a].d[i].min=e[a].d[i].max=k;
while(i>>=1)update(a,i);
}
else
if(y<=((e[a].l+e[a].r)>>1))change(x,y,k,LS(a));
else change(x,y,k,RS(a));
change2(x,a,1);
}
pii query2(int l,int r,int a,int b)
{
N2&k=e[a].d[b];
if(l<=k.l&&k.r<=r)return mkp(k.min,k.max);
pii tot=mkp(INT_MAX,INT_MIN),tmp;
if(l<=((k.l+k.r)>>1))
tmp=query2(l,r,a,LS(b)),
tot.first=min(tot.first,tmp.first),
tot.second=max(tot.second,tmp.second);
if(r>((k.l+k.r)>>1))
tmp=query2(l,r,a,RS(b)),
tot.first=min(tot.first,tmp.first),
tot.second=max(tot.second,tmp.second);
}
pii query(int x1,int x2,int y1,int y2,int a)
{
if(y1<=e[a].l&&e[a].r<=y2)return query2(x1,x2,a,1);
pii tot=mkp(INT_MAX,INT_MIN),tmp;
if(y1<=((e[a].l+e[a].r)>>1))
tmp=query(x1,x2,y1,y2,LS(a)),
tot.first=min(tot.first,tmp.first),
tot.second=max(tot.second,tmp.second);
if(y2>((e[a].l+e[a].r)>>1))
tmp=query(x1,x2,y1,y2,RS(a)),
tot.first=min(tot.first,tmp.first),
tot.second=max(tot.second,tmp.second);
}
int main()
{
IN(t);
for(int cnt=1;cnt<=t;cnt++)
{
printf("Case #%d:\n",cnt);
IN(n),build1(1,n,1);
for(int i=1,a;i<=n;i++)for(int j=1;j<=n;j++)IN(a),change(i,j,a,1);
IN(m);
for(int i=1,a,b,c;i<=m;i++)
{
IN(a),IN(b),IN(c),c>>=1;
pii d=query(max(a-c,0),min(a+c,n),max(b-c,0),min(b+c,n),1);
printf("%d\n",(d.second+d.first)>>1);
change(a,b,(d.second+d.first)>>1,1);
}
}
return 0;
}