#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;
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);
    }
};

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)
{
    KN=N;
    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");
    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(qq[i-1].broj_veza==N-1)
            O[i]=qq[i-1].price;
        else
            O[i]=-1;
	}
}