#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;

struct grana {
    int a,b,t;
    friend bool operator <(const grana &g1, const grana &g2) { return g1.t < g2.t; }
    friend bool operator >(const grana &g1, const grana &g2) { return g1.t > g2.t; }
    friend bool operator ==(const grana &g1, const grana &g2) { return g1.t == g2.t; }
    friend bool operator <=(const grana &g1, const grana &g2) { return g1.t <= g2.t; }
    friend bool operator >=(const grana &g1, const grana &g2) { return g1.t >= g2.t; }
    friend bool operator !=(const grana &g1, const grana &g2) { return g1.t != g2.t; }
    void budi(int _a,int _b,int _t)
    {
        a=_a;
        b=_b;
        t=_t;
    }
};

int r,c,n;

grana tab[250][250];

//dole je kruskal...

struct skup {
    int n;
    int el[41];
    skup(){n=0;}
    void ubaci(int x)
    {
        el[n]=x;
        ++n;
    }
    void ubaci(skup *sk)
    {
        for(int i=0,m=sk->n;i<m;++i)ubaci(sk->el[i]);
    }
    void ocisti()
    {
        n=0;
    }
};
int brg,zbw;
grana ge[165];
int skupcvora[41];
skup svi[41];
void kruskal()
{
    for(int i=1;i<=n;++i)skupcvora[i]=i;
    for(int i=1;i<=n;++i)
    {
        svi[i].ocisti();
        svi[i].ubaci(i);
    }
    sort(ge,ge+brg);
    int ubacio=0;
    int tez=0;
    for(int ig=0;ig<brg;++ig)
    {
        int skupa=skupcvora[ge[ig].a];
        int skupb=skupcvora[ge[ig].b];
        if(skupa!=skupb)
        {
            ge[ubacio]=ge[ig];
            ++ubacio;
            tez+=ge[ig].t;
            if(svi[skupa].n<=svi[skupb].n)
            {
                for(int i=0,m=svi[skupa].n;i<m;++i)skupcvora[svi[skupa].el[i]]=skupb;
                svi[skupb].ubaci(svi+skupa);
                svi[skupa].ocisti();
            }
        }
    }
    brg=ubacio;
    zbw=tez;
}

struct resenje {
    int brg;
    grana ge[41];
    int zbw;
    bool ok()
    {
        return brg==n-1;
    }
    void budi(grana g)
    {
        brg=1;
        ge[0]=g;
        zbw=g.t;
    }
};
void dodajzak(resenje *res)
{
    for(int i=0;i<res->brg;++i)
        ge[brg++]=res->ge[i];
}
void pisires(resenje *res)
{
    res->brg=brg;
    res->zbw=zbw;
    for(int i=0;i<brg;++i)res->ge[i]=ge[i];
}
resenje rkk[250][250][10];

void resi0()
{
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j)
            rkk[i][j][0].budi(tab[i][j]);
    for(int k=1,d=2;k<8;++k)
    {
        for(int i=1;i+d-1<=r;++i)
            for(int j=1;j+d-1<=c;++j)
            {
                brg=0;
                dodajzak(&rkk[i][j][k-1]);
                dodajzak(&rkk[i][j+d/2][k-1]);
                dodajzak(&rkk[i+d/2][j][k-1]);
                dodajzak(&rkk[i+d/2][j+d/2][k-1]);
                kruskal();
                pisires(&rkk[i][j][k]);
            }
        d*=2;
    }
}

bool okje;
int tezje;
void resi(int x1,int y1,int x2,int y2)
{
    if(x1==x2&&y1==y2)
    {
        okje=(n==2);
        tezje=tab[x1][y1].t;
    }
    int duz=x2-x1+1;
    int vis=y2-y1+1;
    int k=0,d=1;
    while(d<duz)
    {
        ++k;
        d*=2;
    }
    --k;
    d/=2;
    brg=0;
    dodajzak(&rkk[x1][y1][k]);
    dodajzak(&rkk[x2+1-d][y1][k]);
    dodajzak(&rkk[x1][y2+1-d][k]);
    dodajzak(&rkk[x2+1-d][y2+1-d][k]);
    kruskal();
    okje=(brg==n-1);
    tezje=zbw;
}

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)
{
    r=R;
    c=C;
    n=N;
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j)
            tab[i][j].budi(U[i][j],V[i][j],W[i][j]);
    resi0();
    for(int i=1;i<=Q;++i)
    {
        resi(X1[i],Y1[i],X2[i],Y2[i]);
        if(okje)O[i]=tezje;
        else O[i]=-1;
    }
}

int mainn()
{
    system("PAUSE");
    return 0;
}