#include <bits/stdc++.h>
using namespace std;

const int inf = 1<<30, MAXN = 3200 + 10;

struct SegTree {
    int ma[MAXN][MAXN], mi[MAXN][MAXN], n;
    int xo, xleaf, x1, y1, x2, y2, x, y, v, vmax, vmin;

    void query1D(int o, int L, int R) {
        if (y1 <= L && y2 >= R) {
            vmax = max(vmax, ma[xo][o]);
            vmin = min(vmin, mi[xo][o]);
            return;
        }
        int mid = (L + R) >> 1;
        if (y1 <= mid) query1D(o << 1, L, mid);
        if (y2 > mid) query1D(o << 1 | 1, mid + 1, R);
    }
    void query2D(int o, int L, int R) {
        if (x1 <= L && x2 >= R) {
            xo = o; query1D(1, 1, n);
            return;
        }
        int mid = (L + R) >> 1;
        if (x1 <= mid) query2D(o << 1, L, mid);
        if (x2 > mid) query2D(o << 1 | 1, mid + 1, R);
    }
    void modify1D(int o, int L, int R) {
        if (L == R) {
            if (xleaf) ma[xo][o] = mi[xo][o] = v;
            else {
                ma[xo][o] = max(ma[xo << 1][o], ma[xo << 1 | 1][o]);
                mi[xo][o] = min(mi[xo << 1][o], mi[xo << 1 | 1][o]);
            }
            return;
        }
        int mid = (L + R) >> 1;
        if (y <= mid) modify1D(o << 1, L, mid);
        else modify1D(o << 1 | 1, mid + 1, R);
        ma[xo][o] = max(ma[xo][o << 1], ma[xo][o << 1 | 1]);
        mi[xo][o] = min(mi[xo][o << 1], mi[xo][o << 1 | 1]);
    }
    void modify2D(int o, int L, int R) {
        if (L == R) {
            xo = o; xleaf = 1;
            modify1D(1, 1, n);
            return;
        }
        int mid = (L + R) >> 1;
        if (x <= mid) modify2D(o << 1, L, mid);
        else modify2D(o << 1 | 1, mid + 1, R);
        xo = o; xleaf = 0; modify1D(1, 1, n);
    }
    void query(int _x1, int _y1, int _x2, int _y2) {
        x1 = _x1; y1 = _y1; x2 = _x2; y2 = _y2;
        vmax = -inf; vmin = inf;
        query2D(1, 1, n);
    }
    void modify(int _x, int _y, int _v) {
        x = _x; y = _y; v = _v;
        modify2D(1, 1, n);
    }
} Solver;

int N, M;

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++ cas) {
        scanf("%d", &N); Solver.n = N;
        for (int i = 1; i <= N; ++ i) {
            for (int j = 1; j <= N; ++ j) {
                int v; scanf("%d", &v);
                Solver.modify(i, j, v);
            }
        }
        printf("Case #%d:\n", cas);
        for (scanf("%d", &M); M --; ) {
            int x, y, l; scanf("%d%d%d", &x, &y, &l); l /= 2;
            int x1 = max(1, x - l), x2 = min(N, x + l);
            int y1 = max(1, y - l), y2 = min(N, y + l);
            Solver.query(x1, y1, x2, y2);
            int ret = (Solver.vmax + Solver.vmin) / 2;
            Solver.modify(x, y, ret);;
            printf("%d\n", ret);
        }
    }
    return 0;
}