#include<bits/stdc++.h>
using namespace std;
int w[505][505],p[505][505];
int n,q;
int sum[250005],l[250005],cnt[250005];
typedef long long ll;
inline void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>w[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>p[i][j],p[i][j]++;
    for(int i=1;i<=n*n;i++) sum[i]=l[i]=cnt[i]=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        sum[p[i][j]]+=w[i][j];cnt[p[i][j]]++;
        if(i<n)
            if(p[i][j]!=p[i+1][j]) l[p[i][j]]++,l[p[i+1][j]]++;
        if(j<n)
            if(p[i][j]!=p[i][j+1]) l[p[i][j]]++,l[p[i][j+1]]++;
    }cin>>q;
    map<int,multiset<int>> sb;
    for(int i=1;i<=n*n;i++)if(cnt[i])sb[l[i]].insert(sum[i]);
    while(q--){
        int x,y,z;ll A,B,C;cin>>x>>y>>z>>A>>B>>C;z++;
        auto del=[&](int z){
            int a=l[z],b=sum[z];
            if(!cnt[z]) return;
            sb[a].erase(sb[a].find(b));
            if(sb[a].empty()) sb.erase(a);
        };
        auto add=[&](int z){
            int a=l[z],b=sum[z];
            if(!cnt[z]) return;
            sb[a].insert(b);
        };
        if(z!=p[x][y]){
            int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
            int w=p[x][y];
            del(w),del(z);
            for(int d=0;d<4;d++){
                int xx=x+dx[d],yy=y+dy[d];
                if(xx<1||yy<1||xx>n||yy>n) continue;
                if(w!=p[xx][yy])l[w]--;else l[w]++;
                if(z!=p[xx][yy])l[z]++;else l[z]--;
            }cnt[w]--,cnt[z]++;
            sum[w]-=::w[x][y];
            add(w);
            p[x][y]=z;
            sum[z]+=::w[x][y];
            add(z);
        }
        ll ans=-1e18;
        // for(int i=1;i<=n*n;i++) cout<<i<<' '<<l[i]<<' '<<sum[i]<<' '<<cnt[i]<<'\n';
        for(auto &[x,y]:sb){
            ll d=A+C*x;
            if(d<0)ans=max(ans,B*x+d**y.begin());
            else ans=max(ans,B*x+d**y.rbegin());
        }
        cout<<ans<<"\n "[!!q];
    }
}
int main(){
    // string name="A";freopen((name+".in").c_str(),"r",stdin);//freopen((name+".out").c_str(),"w",stdout);
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}