#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=42;
const int M=252;
const int Q=200050;
const int B=25;
const int inf=1e9+7;
int n,q,r,c;
int X[Q],Y[Q],W[Q],ans[Q];
int p[N];
void init(){ for(int i=1;i<=n;i++) p[i]=i;}
int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
vector<int> Merge(vector<int> a, vector<int> b)
{
	int i=0,j=0;
	init();
	vector<int> ans;
	ans.reserve(min(a.size()+b.size(),n-1));
	function<void(int)> Try=[&](int e)
	{
		if(Find(X[e])!=Find(Y[e]))
		{
			Union(X[e],Y[e]);
			ans.pb(e);
		}
	};
	while(i<a.size() || j<b.size())
	{
		if(i==a.size()) Try(b[j++]);
		else if(j==b.size()) Try(a[i++]);
		else if(W[a[i]]<W[b[j]]) Try(a[i++]);
		else Try(b[j++]);
	}
	return ans;
}
const int H=M*M*8;
int ls[H],rs[H],root,tsz,rt[H];
vector<int> node[H];
void Set(int &c, int ss, int se, int qi, int e)
{
	if(!c) c=++tsz;
	if(ss==se)
	{
		vector<int> v;v.pb(e);
		node[c]=Merge(node[c],v);
		return;
	}
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,e);
	else Set(rs[c],mid+1,se,qi,e);
	node[c]=Merge(node[ls[c]],node[rs[c]]);
}
void Set(int &c, int ss, int se, int qi, int y, int e)
{
	if(!c) c=++tsz;
	Set(rt[c],1,::c,y,e);
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,y,e);
	else Set(rs[c],mid+1,se,qi,y,e);
}
vector<int> Get(int c, int ss, int se, int qs, int qe)
{
	if(qs<=ss && qe>=se) return node[c];
	int mid=ss+se>>1;
	if(qe<=mid) return Get(ls[c],ss,mid,qs,qe);
	if(qs>mid) return Get(rs[c],mid+1,se,qs,qe);
	return Merge(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
vector<int> Get(int c, int ss, int se, int qs, int qe, int l, int r)
{
	if(qs<=ss && qe>=se) return Get(rt[c],1,::c,l,r);
	int mid=ss+se>>1;
	if(qe<=mid) return Get(ls[c],ss,mid,qs,qe,l,r);
	if(qs>mid) return Get(rs[c],mid+1,se,qs,qe,l,r);
	return Merge(Get(ls[c],ss,mid,qs,qe,l,r),Get(rs[c],mid+1,se,qs,qe,l,r));
}
void Resi(int _N, int R, int C, int _Q, int** U, int** V, int** _W, int* X1, int* Y1, int* X2, int* Y2, int* O)
{
	n=_N;q=_Q;r=R;c=C;
	for(int i=1;i<=r;i++) for(int j=1;j<=c;j++)
	{
		X[i*M+j]=U[i][j];
		Y[i*M+j]=V[i][j];
		W[i*M+j]=_W[i][j];
	}
	vector<pair<int,int>> srt;
	for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) srt.pb({i,j});
	sort(srt.begin(),srt.end(),[&](pair<int,int> a, pair<int,int> b){ return _W[a.first][a.second]<_W[b.first][b.second];});
	for(auto p:srt)
	{
		int i=p.first;
		int j=p.second;
		Set(root,1,r,i,j,i*M+j);
	}
	for(int i=1;i<=q;i++)
	{
		vector<int> tmp=Get(root,1,r,X1[i],X2[i],Y1[i],Y2[i]);
		if(tmp.size()!=n-1) O[i]=-1;
		else
		{
			O[i]=0;
			for(int e:tmp) O[i]+=W[e];
		}
	}
}