#include<bits/stdc++.h>

 #define LL long long

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 #define piii pair<int, pair<int,int>>

 using namespace std;

 const int N=+;

 const int M=1e4+;

 const int inf=0x3f3f3f3f;

 const LL INF=0x3f3f3f3f3f3f3f3f;

 const int mod=1e9 + ;

 int n, q, ans1, ans2, mx[N << ][N << ], mn[N << ][N << ], Map[N][N];

 void subBuild(int op, int pos, int l, int r, int rt) {

     mx[pos][rt] = -inf;

     mn[pos][rt] = inf;

     if(l == r) {

         if(!op) {

             scanf("%d", &mn[pos][rt]);

             mx[pos][rt] = mn[pos][rt];

         } else {

             mn[pos][rt] = min(mn[pos << ][rt], mn[pos <<  | ][rt]);

             mx[pos][rt] = max(mx[pos << ][rt], mx[pos <<  | ][rt]);

         }

         return;

     }

     int mid = l + r >> ;

     subBuild(op, pos, l, mid, rt << );

     subBuild(op, pos, mid + , r, rt <<  | );

     mn[pos][rt] = min(mn[pos][rt << ], mn[pos][rt <<  | ]);

     mx[pos][rt] = max(mx[pos][rt << ], mx[pos][rt <<  | ]);

 }

 void build(int l, int r, int rt) {

     if(l == r) {

         subBuild(, rt, , n, );

         return;

     }

     int mid = l + r >> ;

     build(l, mid, rt << );

     build(mid + , r, rt <<  | );

     subBuild(, rt, , n, );

 }

 void subUpdate(int op, int pos, int y, int v, int l,int r,int rt) {

     if(l == r) {

         if(!op) mn[pos][rt] = mx[pos][rt] = v;

         else {

             mn[pos][rt] = min(mn[pos << ][rt], mn[pos <<  | ][rt]);

             mx[pos][rt] = max(mx[pos << ][rt], mx[pos <<  | ][rt]);

         }

         return;

     }

     int mid = l + r >> ;

     if(y <= mid) subUpdate(op, pos, y, v, l, mid, rt << );

     else subUpdate(op, pos, y, v, mid + ,r, rt <<  | );

     mn[pos][rt] = min(mn[pos][rt << ], mn[pos][rt <<  | ]);

     mx[pos][rt] = max(mx[pos][rt << ], mx[pos][rt <<  | ]);

 }

 void update(int x, int y, int v, int l, int r, int rt) {

     if(l == r) {

         subUpdate(, rt, y, v, , n, );

         return;

     }

     int mid = l + r >> ;

     if(x <= mid) update(x, y, v, l, mid, rt << );

     else update(x, y, v, mid + , r, rt <<  | );

     subUpdate(, rt, y, v, , n, );

 }

 void subQuery(int L, int R, int pos, int l, int r, int rt) {

     if(l >= L && r <= R) {

         ans1 = min(ans1, mn[pos][rt]);

         ans2 = max(ans2, mx[pos][rt]);

         return;

     }

     int mid = l + r >> ;

     if(L <= mid) subQuery(L, R, pos, l, mid , rt << );

     if(R > mid) subQuery(L, R, pos, mid + , r, rt <<  | );

 }

 void query(int Lx, int Rx, int Ly, int Ry, int l, int r, int rt) {

     if(l >= Lx && r <= Rx) {

         subQuery(Ly, Ry, rt, , n, );

         return;

     }

     int mid = l + r >> ;

     if(Lx <= mid) query(Lx, Rx, Ly, Ry, l, mid, rt << );

     if(Rx > mid) query(Lx, Rx, Ly, Ry, mid + , r, rt <<  | );

 }

 int main() {

     int T; scanf("%d", &T);

     for(int cas = ; cas <= T; cas++) {

         printf("Case #%d:\n", cas);

         scanf("%d", &n);

         build(, n, );

         scanf("%d", &q);

         while(q--) {

             int x, y, w; scanf("%d%d%d", &x, &y, &w);

             w >>= ;

             int r1 = max(, x - w);

             int r2 = min(n, x + w);

             int c1 = max(, y - w);

             int c2 = min(n, y + w);

             ans1 = inf, ans2 = -inf;

             query(r1, r2, c1, c2, , n, );

             printf("%d\n", ans1 + ans2 >> );

             update(x, y, ans1 + ans2 >> , , n, );

         }

     }

     return ;

 }

 /*

 */