#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;

#define vi vector<int>
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define rep(i,n) for (int i=0;i<(n);i++)
#define req(i,n) for (int i=1;i<(n);i++)

struct node {
	int minv,maxv;
	node(){int _minv = 0x7fffffff,_maxv = -1;minv=_minv;maxv=_maxv;}
};
node zero;
node tree[3233][3233];
int m[850][850];
int n;

#define debug(x) cout << #x << " = " << x <<endl
const int maxn = 100001;

void maketreey(int xid,int up,int down,int yid,int left,int right)
{
	if (left!=right)
	{
		int mid=(left+right)>>1;
		maketreey(xid,up,down,yid<<1,left,mid);
		maketreey(xid,up,down,(yid<<1)+1,mid+1,right);
	}
	if (left==right && up==down)
	{
		tree[xid][yid].minv = tree[xid][yid].maxv = m[up][left];
	}else{
		if (left!=right)
		{
			tree[xid][yid].minv = min(tree[xid][yid<<1].minv,tree[xid][(yid<<1)+1].minv);
			tree[xid][yid].maxv = max(tree[xid][yid<<1].maxv,tree[xid][(yid<<1)+1].maxv);
		}else{
			tree[xid][yid].minv = min(tree[xid<<1][yid].minv,tree[(xid<<1)+1][yid].minv);
			tree[xid][yid].maxv = max(tree[xid<<1][yid].maxv,tree[(xid<<1)+1][yid].maxv);
		}
	}
//	cout << xid << ' ' << up << ' ' << down << "  y=" << yid << ' ' << left << ' ' << right << " minv=" 	<< tree[xid][yid].minv << " maxv=" << tree[xid][yid].maxv << endl;
}

void maketreex(int xid,int up,int down)
{
	if (up!=down)
	{
		int mid = (up+down) >> 1;
		maketreex(xid<<1,up,mid);
		maketreex((xid<<1)+1,mid+1,down);
	}
	maketreey(xid,up,down,1,1,n);
}

node searchy(int xid,int yid,int left,int right,int leftlim,int rightlim)
{
	if (left>rightlim || right < leftlim) return zero;
	if (leftlim <= left && right <= rightlim)
	{
		return tree[xid][yid];
	}else
	{
		int mid=(left+right)>>1;
		node toreturn=zero,t;

		if (left!=right){
			t = searchy(xid,yid<<1,left,mid,leftlim,rightlim);
			toreturn.minv = min(toreturn.minv,t.minv);
			toreturn.maxv = max(toreturn.maxv,t.maxv);

			t = searchy(xid,(yid<<1)+1,mid+1,right,leftlim,rightlim);
			toreturn.minv = min(toreturn.minv,t.minv);
			toreturn.maxv = max(toreturn.maxv,t.maxv);
		}
		return toreturn;
	}
}

node searchx(int xid,int up,int down,int uplim,int downlim,int leftlim,int rightlim)
{
	if (up>downlim || down<uplim) return zero;
	if (uplim<=up && down <= downlim)
	{
		return searchy(xid,1,1,n,leftlim,rightlim);
	}else
	{
		int mid=(up+down)>>1;
		node toreturn=zero,t;

		if (downlim <= mid) return searchx(xid<<1,up,mid,uplim,downlim,leftlim,rightlim);
		if (mid+1 <= uplim) return searchx((xid<<1)+1,mid+1,down,uplim,downlim,leftlim,rightlim);
		
		if (up!=down)
		{
			t = searchx(xid<<1,up,mid,uplim,downlim,leftlim,rightlim);
			toreturn.minv = min(toreturn.minv,t.minv);
			toreturn.maxv = max(toreturn.maxv,t.maxv);

			t = searchx((xid<<1)+1,mid+1,down,uplim,downlim,leftlim,rightlim);
			toreturn.minv = min(toreturn.minv,t.minv);
			toreturn.maxv = max(toreturn.maxv,t.maxv);
		}
		return toreturn;
	}
}

void changey(int xid,int up,int down,int yid,int left,int right,int x,int y,int value)
{
	if (y < left || y > right) return;
	int mid=(left+right)>>1;
	if (left!=right){

	
		changey(xid,up,down,yid<<1,left,mid,x,y,value);
		changey(xid,up,down,(yid<<1)+1,mid+1,right,x,y,value);
		tree[xid][yid].minv = min(tree[xid][yid<<1].minv,tree[xid][(yid<<1)+1].minv);
		tree[xid][yid].maxv = max(tree[xid][yid<<1].maxv,tree[xid][(yid<<1)+1].maxv);
	}else{
		if (up==down)
		{
			tree[xid][yid].minv = tree[xid][yid].maxv = value;
		}else{
			tree[xid][yid].minv = min(tree[xid<<1][yid].minv,tree[(xid<<1)+1][yid].minv);
			tree[xid][yid].maxv = max(tree[xid<<1][yid].maxv,tree[(xid<<1)+1][yid].maxv);	
		}
	}
}

void changex(int xid,int up,int down,int x,int y,int value)
{
	if (x<up || down < x) return;
	if (up != down) {
		int mid=(up+down)>>1;
		changex(xid<<1,up,mid,x,y,value);
		changex((xid<<1)+1,mid+1,down,x,y,value);
	}
	changey(xid,up,down,1,1,n,x,y,value);
}

int main()
{
	int T;
	//freopen("Gt.in","r",stdin);
	cin >> T;
	for (int tt=1;tt<=T;tt++)
	{
		int q;
		printf("Case #%d:\n",tt);
		//cout << "Case #" << tt << ":" << endl;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				scanf("%d",&m[i][j]);
		maketreex(1,1,n);
		scanf("%d",&q);
		for (int i=1;i<=q;i++)
		{
			int x,y,len;
			scanf("%d %d %d",&x,&y,&len);
			len >>= 1;
			node t = searchx(1,1,n,max(1,x-len),min(n,x+len),max(1,y-len),min(n,y+len));
			/*for (int xid=1;xid<=5;xid++){
				for (int yid=1;yid<=5;yid++)
					cout << xid << " " << yid << " " << tree[xid][yid].minv << " " << tree[xid][yid].maxv << endl;
			}*/
		//	cout << x << " " << y << " " << t.minv << ' ' << t.maxv << "      v=";
			int value = (t.minv+t.maxv)>>1;
			printf("%d\n",value);
			changex(1,1,n,x,y,value);
			//m[x][y] = value;
			//maketreex(1,1,n);
		}
	}
	return 0;
}