#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>
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++;
    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)
{
    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]);
    u=U;
    v=V;
    w=W;
    n=R;
    m=C;
    KN=N;
    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;
    }
}