# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,mx[500010],mn[500010],a[510][510],p[510][510],sum[250010],cnt[250010],len[250010],t[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
multiset<int> st[500010];
struct Arr
{
	vector<int> legal;
	int tot,c[500010],pos[500010];
	void init(int t)
	{
		tot=t;legal.clear();
		for(int i=0;i<=tot;i++) pos[i]=-1,c[i]=0;
	}
	void Inc(int i)
	{
		if(!c[i]) pos[i]=legal.size(),legal.push_back(i);
		c[i]++;
	}
	void Dec(int i)
	{
		if(c[i]==1)
		{
			swap(legal[pos[i]],legal.back());pos[legal[pos[i]]]=pos[i];
			legal.pop_back();pos[i]=-1;
		}
		c[i]--;
	}
}Ar;
void pushup(int i)
{
	if(st[i].empty()) mn[i]=1e9,mx[i]=-1e9;
	else mn[i]=*st[i].begin(),mx[i]=*--st[i].end();
}
void Insert(int i)
{
	if(!cnt[i]) return;
	Ar.Inc(len[i]);st[len[i]].insert(sum[i]);
	pushup(len[i]);
}
void Erase(int i)
{
	if(!cnt[i]) return;
	Ar.Dec(len[i]);st[len[i]].erase(st[len[i]].find(sum[i]));
	pushup(len[i]);
}
ll query(ll A,ll B,ll C)
{
	ll ans=-1e18;
	for(int l:Ar.legal)
	{
		if(st[l].empty()) continue;
		ll k=A+C*l,b=B*l;
		ans=max(ans,max(k*mn[l]+b,k*mx[l]+b));
	}
	return ans;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&p[i][j]),cnt[p[i][j]]++,sum[p[i][j]]+=a[i][j];
		for(int i=1;i<n;i++)
			for(int j=1;j<=n;j++)
				if(p[i][j]!=p[i+1][j])
					len[p[i][j]]++,len[p[i+1][j]]++;
		for(int i=1;i<=n;i++)
			for(int j=1;j<n;j++)
				if(p[i][j]!=p[i][j+1])
					len[p[i][j]]++,len[p[i][j+1]]++;
		Ar.init(2*n*n);
		for(int i=0;i<=2*n*n;i++) st[i].clear(),mn[i]=1e9,mx[i]=-1e9;
		for(int i=0;i<n*n;i++) Insert(i);
		int q;
		scanf("%d",&q);
		while(q--)
		{
			int x,y,z;
			ll A,B,C;
			scanf("%d%d%d%lld%lld%lld",&x,&y,&z,&A,&B,&C);
			vector<int> vec={p[x][y],z};
			for(int i=0;i<4;i++)
			{
				int tx=x+t[i][0],ty=y+t[i][1];
				if(tx>=1 && tx<=n && ty>=1 && ty<=n) vec.push_back(p[tx][ty]);
			}
			sort(vec.begin(),vec.end());
			vec.erase(unique(vec.begin(),vec.end()),vec.end());
			for(int i:vec) Erase(i);
			for(int i=0;i<4;i++)
			{
				int tx=x+t[i][0],ty=y+t[i][1];
				if(tx<1 || tx>n || ty<1 || ty>n) continue;
				if(p[tx][ty]!=p[x][y]) len[p[tx][ty]]--,len[p[x][y]]--;
			}
			sum[p[x][y]]-=a[x][y];cnt[p[x][y]]--;
			p[x][y]=z;
			sum[p[x][y]]+=a[x][y];cnt[p[x][y]]++;
			for(int i=0;i<4;i++)
			{
				int tx=x+t[i][0],ty=y+t[i][1];
				if(tx<1 || tx>n || ty<1 || ty>n) continue;
				if(p[tx][ty]!=p[x][y]) len[p[tx][ty]]++,len[p[x][y]]++;
			}
			for(int i:vec) Insert(i);
			printf("%lld%c",query(A,B,C)," \n"[!q]);
		}
		for(int i=0;i<=2*n*n;i++) sum[i]=cnt[i]=len[i]=0;
	}
	return 0;
}