// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

using namespace std;

const int maxn = 525;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector p(n, vector<int>(n));
        vector v(n, vector<int>(n));
        vector<int64_t> w(n * n);
        vector<int> l(n * n);
        vector<int> c(n * n);

        map<int, multiset<int64_t>> mp;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> v[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> p[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                w[p[i][j]] += v[i][j];
                c[p[i][j]] += 1;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j + 1 < n; j++) {
                if (p[i][j] != p[i][j + 1]) {
                    l[p[i][j]] += 1;
                    l[p[i][j+1]] += 1;
                }
            }
        }
        for (int i = 0; i + 1 < n; i++) {
            for (int j = 0; j < n; j++) {
                if (p[i][j] != p[i+1][j]) {
                    l[p[i][j]] += 1;
                    l[p[i+1][j]] += 1;
                }
            }
        }

        for (int i = 0; i < n*n; i++) {
            if (c[i] > 0) {
                mp[l[i]].insert(w[i]);
            }
            // cerr << l[i] << ',' << w[i] << endl;
        }

        // assert (mp.size() <= n);


        int q;
        cin >> q;
        for (int it = 0; it < q; it++) {
            int i, j, np;
            cin >> i >> j >> np;
            --i, --j;
            
            for (int coef: {-1, 1}) {
                for (int dir = 0; dir < 4; dir++) {
                    int ni = i + dx[dir];
                    int nj = j + dy[dir];
                    if (ni >= 0 && nj >= 0 && ni < n && nj < n) {
                        if (p[i][j] != p[ni][nj]) {
                            for (int P: {p[i][j], p[ni][nj]}) {
                                auto &ms = mp[l[P]];
                                if (c[P] == 0) continue;
                                // cerr << P << ';' << l[P] << ',' << w[P] << endl;
                                // auto it = ms.find(w[P]);
                                // assert (it != ms.end());
                                ms.erase(ms.find(w[P]));
                                if (ms.empty())
                                    mp.erase(l[P]);
                            }
                            l[p[i][j]] += coef;
                            l[p[ni][nj]] += coef;
                            for (int P: {p[i][j], p[ni][nj]}) {
                                auto &ms = mp[l[P]];
                                if (c[P] == 0) continue;
                                ms.insert(w[P]);
                            }
                        }
                    }
                }
                {
                    int P = p[i][j];
                    auto &ms = mp[l[P]];
                    if (c[P] > 0)
                        ms.erase(ms.find(w[P]));
                    c[P] += coef;
                    w[P] += coef * v[i][j];
                    if (c[P] > 0)
                        ms.insert(w[P]);
                }
                p[i][j] = np;
            }

            int64_t A, B, C;
            cin >> A >> B >> C;

            int64_t ans = -1e18;
            for (auto &[L, ms]: mp) {
                if (ms.empty()) continue;
                for (int64_t W: {*ms.begin(), *prev(ms.end())}) {
                    ans = max(ans, A * W + B * L + C * W * L);
                }
            }
            cout << ans << (it + 1 == q ? '\n' : ' ');
        }
    }
}