#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=810;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
struct Tree
{
    int mav[maxn<<2][maxn<<2],miv[maxn<<2][maxn<<2];
    int n,m,x,y,val,isleaf,x1,y1,x2,y2,xrt,amav,amiv;
    void buildy(int L,int R,int rt)
    {
        if(L==R)
        {
            if(isleaf)
            {
                scanf("%d",&mav[xrt][rt]);
                miv[xrt][rt]=mav[xrt][rt];
            }
            else
            {
                mav[xrt][rt]=max(mav[xrt<<1][rt],mav[xrt<<1|1][rt]);
                miv[xrt][rt]=min(miv[xrt<<1][rt],miv[xrt<<1|1][rt]);
            }
            return;
        }
        int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
        buildy(lson);
        buildy(rson);
        mav[xrt][rt]=max(mav[xrt][ls],mav[xrt][rs]);
        miv[xrt][rt]=min(miv[xrt][ls],miv[xrt][rs]);
    }
    void buildx(int L,int R,int rt)
    {
        if(L==R)
        {
            xrt=rt,isleaf=1;
            buildy(1,m,1);
            return;
        }
        int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
        buildx(lson);
        buildx(rson);
        xrt=rt,isleaf=0;
        buildy(1,m,1);
    }
    void build(int nn,int mm)
    {
        n=nn,m=mm;
        buildx(1,n,1);
    }
    void updatey(int L,int R,int rt)
    {
        if(L==R)
        {
            if(isleaf)
                mav[xrt][rt]=miv[xrt][rt]=val;
            else
            {
                mav[xrt][rt]=max(mav[xrt<<1][rt],mav[xrt<<1|1][rt]);
                miv[xrt][rt]=min(miv[xrt<<1][rt],miv[xrt<<1|1][rt]);
            }
            return;
        }
        int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
        if(y<=mid)
            updatey(lson);
        else
            updatey(rson);
        mav[xrt][rt]=max(mav[xrt][ls],mav[xrt][rs]);
        miv[xrt][rt]=min(miv[xrt][ls],miv[xrt][rs]);
    }
    void updatex(int L,int R,int rt)
    {
        if(L==R)
        {
            xrt=rt,isleaf=1;
            updatey(1,m,1);
            return;
        }
        int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
        if(x<=mid)
            updatex(lson);
        else
            updatex(rson);
        xrt=rt,isleaf=0;
        updatey(1,m,1);
    }
    void update(int xx,int yy,int v)
    {
        x=xx,y=yy,val=v;
        updatex(1,n,1);
    }
    void queryy(int L,int R,int rt)
    {
        if(y1<=L&&R<=y2)
        {
            amav=max(amav,mav[xrt][rt]);
            amiv=min(amiv,miv[xrt][rt]);
            return;
        }
        int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
        if(y1<=mid)
            queryy(lson);
        if(y2>mid)
            queryy(rson);
    }
    void queryx(int L,int R,int rt)
    {
        if(x1<=L&&R<=x2)
        {
            xrt=rt;
            queryy(1,m,1);
            return;
        }
        int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
        if(x1<=mid)
            queryx(lson);
        if(x2>mid)
            queryx(rson);
    }
    void query(int xx1,int yy1,int xx2,int yy2)
    {
        x1=xx1,y1=yy1,x2=xx2,y2=yy2;
        amav=-1,amiv=INF;
        queryx(1,n,1);
    }
} tree;
int main()
{
    int t,cas=1,n,m,i,x,y,len,x1,y1,x2,y2,ans;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        tree.build(n,n);
        printf("Case #%d:\n",cas++);
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&len);
            len=len>>1;
            x1=max(1,x-len),y1=max(1,y-len);
            x2=min(n,x+len),y2=min(n,y+len);
            tree.query(x1,y1,x2,y2);
            ans=(tree.amav+tree.amiv)>>1;
            tree.update(x,y,ans);
            printf("%d\n",ans);
        }
    }
    return 0;
}