#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()

using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
namespace prva{
const int M=250,NN=40;
int KN;
struct query{
    vector<int> par;
    int broj_veza,price;
    query(){par.resize(NN);broj_veza=0;price=0;for(int i=0;i<NN;i++)par[i]=i;}
    int find(int tr)
    {
        if(par[tr]==tr)
            return tr;
        return par[tr]=find(par[tr]);
    }
    void merge(int a,int b,int p)
    {
        a=find(a);b=find(b);
        if(a==b)
            return;
        broj_veza++;
        price+=p;
        par[a]=b;
    }
};
vector<query> qq;
struct segTree{
    vector<vector<int> > ima;
    segTree(){ima.resize(4*M);}
    void dodaj(int qs,int qe,int x,int l=0,int r=M-1,int i=1)
    {
        if(qs>r||qe<l)
            return;
        if(qs<=l&&qe>=r)
        {
            ima[i].pb(x);
            return;
        }
        int m=(l+r)>>1;
        dodaj(qs,qe,x,l,m,2*i);
        dodaj(qs,qe,x,m+1,r,2*i+1);
    }
    void add(int pos,int u,int v,int price,int l=0,int r=M-1,int i=1)
    {
        //printf("Add2 %i %i  %i\n",l,r,i);
        if(l>pos||r<pos)
            return;
        for(auto p:ima[i]){
            //printf("%i  %i-%i  %i\n",p,u,v,price);
            qq[p].merge(u,v,price);
        }
        if(l==r)
            return;
        int m=(l+r)>>1;
        add(pos,u,v,price,l,m,2*i);
        add(pos,u,v,price,m+1,r,2*i+1);
    }
};
struct seg2d{
    vector<segTree> yes;
    seg2d(){yes.resize(4*M);}
    void dodaj(int qs,int qe,int l1,int r1,int x,int l=0,int r=M-1,int i=1)
    {
        if(qs>r||qe<l)
            return;
        if(qs<=l&&qe>=r)
        {
            //printf("%i-%i!\n",qs,qe);
            yes[i].dodaj(l1,r1,x);
            return;
        }
        if(l==r)
            return;
        int m=(l+r)>>1;
        dodaj(qs,qe,l1,r1,x,l,m,2*i);
        dodaj(qs,qe,l1,r1,x,m+1,r,2*i+1);
    }
    void add(int x,int y,int u,int v,int price,int l=0,int r=M-1,int i=1)
    {
        //printf("Add %i %i %i\n",l,r,i);
        if(l>x||r<x)
            return;
        yes[i].add(y,u,v,price);
        if(l==r)
            return;
        int m=(l+r)>>1;
        add(x,y,u,v,price,l,m,2*i);
        add(x,y,u,v,price,m+1,r,2*i+1);
    }
};
};
namespace druga{
const int M=250,NN=40;
int KN,n,m;
int **u,**v,**w;
vector<pair<pair<int,int>,int> > merge(vector<pair<pair<int,int>,int> > lft,vector<pair<pair<int,int>,int> > rght)
{
    int trl=0,trr=0;
    vector<pair<pair<int,int>,int> > sol;
    while(trl<(int)lft.size()&&trr<(int)rght.size())
    {
        if(lft[trl].f==rght[trr].f)
        {
            sol.pb({lft[trl].f,min(lft[trl].s,rght[trr].s)});
            trl++;
            trr++;
            continue;
        }
        if(lft[trl].f<rght[trr].f)
        {
            sol.pb(lft[trl]);
            trl++;
            continue;
        }
        sol.pb(rght[trr]);
        trr++;
    }
    while(trl<(int)lft.size())
        sol.pb(lft[trl]),trl++;
    while(trr<(int)rght.size())
        sol.pb(rght[trr]),trr++;
    assert(sol.size()<=3);
    return sol;
}
vector<pair<pair<int,int>,int> > e;
struct segTree{
    vector<vector<pair<pair<int,int>,int> > > ima;
    segTree(){ima.resize(512);}
    void build(int x,int l=0,int r=m-1,int i=1)
    {
        if(l==r)
        {
            ima[i].pb({{u[x+1][l+1]-1,v[x+1][l+1]-1},w[x+1][l+1]});
            //printf("%i %i %i\n",ima[i].back().f.f,ima[i].back().f.s,ima[i].back().s);
            return;
        }
        int m=(l+r)>>1;
        build(x,l,m,2*i);
        build(x,m+1,r,2*i+1);
        ima[i]=merge(ima[2*i],ima[2*i+1]);
    }
    vector<pair<pair<int,int>,int> > get(int qs,int qe,int l=0,int r=m-1,int i=1)
    {
        if(qs>r||qe<l)
            return e;
        if(qs<=l&&qe>=r)
        {
            return ima[i];
        }
        int m=(l+r)>>1;
        return merge(get(qs,qe,l,m,2*i),get(qs,qe,m+1,r,2*i+1));
    }
};
struct seg2d{
    vector<segTree> yes;
    seg2d(){yes.resize(512);}
    void build(int l=0,int r=n-1,int i=1)
    {
        if(l==r)
        {
            yes[i].build(l);
            return;
        }
        int m=(l+r)>>1;
        build(l,m,2*i);
        build(m+1,r,2*i+1);
        for(int j=1;j<512;j++)
        {
            yes[i].ima[j]=merge(yes[2*i].ima[j],yes[2*i+1].ima[j]);
        }
    }
    vector<pair<pair<int,int>,int> > get(int qs,int qe,int l1,int r1,int l=0,int r=n-1,int i=1)
    {
        if(qs>r||qe<l)
            return e;
        if(qs<=l&&qe>=r)
        {
            return yes[i].get(l1,r1);
        }
        int m=(l+r)>>1;
        return merge(get(qs,qe,l1,r1,l,m,2*i),get(qs,qe,l1,r1,m+1,r,2*i+1));
    }
};
};
bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b)
{
    if(a.s==b.s)
        return a.f<b.f;
    return a.s<b.s;
}
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)
{
    if(N==2)
    {
        for(int i=1;i<=R;i++)
            for(int j=1;j<=C;j++)
                if(U[i][j]>V[i][j])
                    swap(U[i][j],V[i][j]);
        druga::u=U;
        druga::v=V;
        druga::w=W;
        druga::n=R;
        druga::m=C;
        druga::KN=N;
        druga::seg2d st;
        st.build();
        for(int i=1;i<=Q;i++)
        {
            vector<pair<pair<int,int>,int> > edges=st.get(X1[i]-1,X2[i]-1,Y1[i]-1,Y2[i]-1);
            /*for(auto p:edges)
                printf("%i-%i %i\n",p.f.f,p.f.s,p.s);*/
            sort(all(edges),cmp);
            vector<int> par(N);
            int price=0,cnt=0;
            for(int i=0;i<N;i++)
                par[i]=i;
            function<int(int)> find=[&](int tr){
                if(par[tr]==tr)
                    return tr;
                return par[tr]=find(par[tr]);
            };
            auto merge=[&](int a,int b,int w)
            {
                a=find(a);
                b=find(b);
                if(a==b)
                    return;
                price+=w;
                cnt++;
            };
            for(auto p:edges)
                merge(p.f.f,p.f.s,p.s);
            if(cnt==N-1)
                O[i]=price;
            else
                O[i]=-1;
        }
        return;
    }
    prva::KN=N;
    prva::seg2d st;
    vector<pair<int,pair<pair<int,int>,pair<int,int> > > > edges;
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
            edges.pb({W[i][j],{{U[i][j]-1,V[i][j]-1},{i-1,j-1}}});
    sort(all(edges));
    //printf("Uradio edges!\n");
    prva::qq.resize(Q);
    for(int i=1;i<=Q;i++)
        st.dodaj(X1[i]-1,X2[i]-1,Y1[i]-1,Y2[i]-1,i-1);
    //printf("Dodao!\n");
    for(auto p:edges)
        st.add(p.s.s.f,p.s.s.s,p.s.f.f,p.s.f.s,p.f);
    //printf("Adovao!\n");
	for (int i=1; i<=Q; i++)
	{
	    if(prva::qq[i-1].broj_veza==N-1)
            O[i]=prva::qq[i-1].price;
        else
            O[i]=-1;
	}
}