#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Grana
{
    int u;
    int v;
    int w;
};

bool cmp(Grana g1, Grana g2)
{
    return (g1.w<g2.w);
}

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<=Q;i++)
        {
            int x1=X1[i], y1=Y1[i],x2=X2[i],y2=Y2[i];
            if(N==2)
            {
                int minn=-1;
                for(int k=x1;i<=x2;i++)
                {
                    for(int j=y1;j<=y2;j++)
                    {
                        if(minn==-1) minn=W[k][j];
                        if(W[k][j]<minn) minn=W[k][j];
                    }
                }
                O[i]=minn;
            }
            else if(N==3)
            {
                int minn1=-1,minn2=-1,minn3=-1,br=3;
                for(int j=x1;j<=x2;j++)
                {
                    for(int k=y1;k<=y2;k++)
                    {
                        if(U[j][k]*V[j][k]==2)
                        {
                            if(minn1<0)
                            {
                                minn1=W[j][k];
                                br--;
                            }
                            if(W[j][k]<minn1) minn1=W[j][k];
                        }
                        if(U[j][k]*V[j][k]==3)
                        {
                            if(minn2<0)
                            {
                                minn2=W[j][k];
                                br--;
                            }
                            if(W[j][k]<minn2) minn2=W[j][k];
                        }
                        if(U[j][k]*V[j][k]==6)
                        {
                            if(minn3<0)
                            {
                                minn3=W[j][k];
                                br--;
                            }
                            if(W[j][k]<minn3) minn3=W[j][k];
                        }
                    }
                }
                if(br>1) O[i]=-1;
                else if(br==1) O[i]=minn1+minn2+minn3+1;
                else O[i]=minn1+minn2+minn3-max(max(minn1,minn2),minn3);
            }
            else
            {
                vector<Grana> grane;
                for(int j=x1;j<=x2;j++)
                {
                    for(int k=y1;k<=y2;k++)
                    {
                        Grana g;
                        g.u=U[j][k];
                        g.v=V[j][k];
                        g.w=W[j][k];
                        grane.push_back(g);
                    }
                }
                sort(grane.begin(),grane.end(),cmp);
                long long mst=0;
                vector<int> koren(N+1);
                for(int j=1;j<=N;j++) koren[j]=-1;
                int brojac=0;
                for(int j=0;j<grane.size();j++)
                {
                    Grana g;
                    g=grane[j];
                    int kor1=koren[g.u],kor2=koren[g.v];
                    int cvor1=g.u,cvor2=g.v;
                    while(kor1>0)
                    {
                        cvor1=kor1;
                        kor1=koren[kor1];
                        //cout << "1."  << i << " " << cvor1 << " " << kor1 << endl;
                    }
                    while(kor2>0)
                    {
                        cvor2=kor2;
                        kor2=koren[kor2];
                        //cout << "2." << i << " " << cvor2 << " " << kor2 << endl;
                    }
                    if(cvor1!=cvor2)
                    {
                        brojac++;
                        mst+=g.w;
                        if(kor1<kor2)
                        {
                            koren[cvor1]+=koren[cvor2];
                            koren[cvor2]=cvor1;
                        }
                        else
                        {
                            koren[cvor2]+=koren[cvor1];
                            koren[cvor1]=cvor2;
                        }
                    }
                    if(brojac==N-1) break;
                }
                if(brojac!=N-1) O[i]=-1;
                else O[i]=mst;
            }
        }
	}