#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;
int n,q,r,c;
struct Event
{
	int x1,x2,y1,y2,id;
	Event(){}
	Event(int a, int b, int c, int d, int e)
	{
		x1=a;
		x2=b;
		y1=c;
		y2=d;
		id=e;
	}
	bool operator < (Event b) const
	{
		return mp(mp(x1/B,x2/B),mp(y1/B,y2))<mp(mp(b.x1/B,b.x2/B),mp(b.y1/B,b.y2));
	}
};
struct Work
{
	int l,r,id;
	Work(){}
	Work(int a, int b, int c):l(a),r(b),id(c){}
};
vector<Work> work;
vector<Event> es;
int tme[M][M];
void Del(int x1, int x2, int y1, int y2, int t)
{
	for(int i=x1;i<=x2;++i) for(int j=y1;j<=y2;++j)
	{
		if(tme[i][j]) work.pb(Work(tme[i][j],t-1,i*M+j));
		tme[i][j]=0;
	}
}
void Add(int x1, int x2, int y1, int y2, int t)
{
	//printf("Add: %i %i %i %i  %i\n",x1,x2,y1,y2,t);
	for(int i=x1;i<=x2;++i) for(int j=y1;j<=y2;++j)
	{
		tme[i][j]=t;
		//printf("Add:%i %i at time %i\n",i,j,t);
	}
}
void ClearAll(int t)
{
	for(int i=1;i<=r;++i) for(int j=1;j<=c;++j)
	{
		if(tme[i][j]) work.pb(Work(tme[i][j],t,i*M+j));
		tme[i][j]=0;
	}
}
void Move(int &XL, int &XR, int &YL, int &YR, Event e, int t)
{
	//printf("((%i %i),(%i %i))->((%i %i),(%i %i))\n",XL,XR,YL,YR,e.x1,e.x2,e.y1,e.y2);
	if(max(XL,e.x1)>min(XR,e.x2) || max(YL,e.y1)>min(YR,e.y2))
	{
		//printf(":D\n");
		Del(XL,XR,YL,YR,t);
		Add(e.x1,e.x2,e.y1,e.y2,t);
	}
	else
	{
		Del(XL,e.x1-1,YL,YR,t);
		Del(e.x2+1,XR,YL,YR,t);
		Del(XL,XR,YL,e.y1-1,t);
		Del(XL,XR,e.y2+1,YR,t);
		Add(e.x1,XL-1,e.y1,e.y2,t);
		Add(XR+1,e.x2,e.y1,e.y2,t);
		Add(e.x1,e.x2,e.y1,YL-1,t);
		Add(e.x1,e.x2,YR+1,e.y2,t);
	}
	XL=e.x1;XR=e.x2;
	YL=e.y1;YR=e.y2;
}
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;
	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;
}
void Solve(int ss, int se, vector<Work> work, vector<int> edges)
{
	vector<Work> L,R;
	vector<int> now;
	int mid=ss+se>>1;
	for(Work w:work)
	{
		if(w.l<=ss && w.r>=se) now.pb(w.id);
		else
		{
			if(w.r>mid) R.pb(w);
			if(w.l<=mid) L.pb(w);
		}
	}
	edges=Merge(edges,now);
	if(ss==se)
	{
		if(edges.size()!=n-1) ans[ss]=-1;
		else
		{
			for(int i=0;i<edges.size();i++) ans[ss]+=W[edges[i]];
		}
	}
	else
	{
		Solve(ss,mid,L,edges);
		Solve(mid+1,se,R,edges);
	}
}
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<=q;i++) es.pb(Event(X1[i],X2[i],Y1[i],Y2[i],i));
	sort(es.begin(),es.end());
	int XL=0,XR=-1,YL=0,YR=-1;
	int t=0;
	for(Event e:es) t++,Move(XL,XR,YL,YR,e,t);
	ClearAll(t);
	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];
	}
	sort(work.begin(),work.end(),[&](Work a, Work b){ return W[a.id]<W[b.id];});
	/*for(Work w:work)
	{
		printf("(%i %i) %i\n",w.l,w.r,w.id);
	}*/
	Solve(1,q,work,vector<int>());
	for(int i=1;i<=q;i++)
	{
		O[es[i-1].id]=ans[i];
	}
}