#include <bits/stdc++.h>
#define maxn 53
#define maxr 290
#define inf 1e9
using namespace std;

int p[maxn], ans;
vector<pair<int, pair<int, int> > > es;

int findP(int x){
    if(x == p[x]){
        return p[x];
    }
    return p[x] = findP(p[x]);
}

bool join(int x, int y){
    x = findP(x);
    y = findP(y);
    if(x == y){
        return 0;
    }
    p[x] = y;
    return true;
}

struct segTr{
    int segT[maxr];
    void init(int idx, int l, int r, int *a){
        if(l == r){
            segT[idx] = a[l];
            return;
        }
        int mid = (l+r)/2;
        init(idx*2+1, l, mid, a);
        init(idx*2+2, mid+1, r, a);
        segT[idx] = min(segT[idx*2+1], segT[idx*2+2]);
    }
    void update(int idx, int l, int r, int x, int val){
        if(l == r){
            segT[idx] = val;
            return;
        }
        int mid = (l+r)/2;
        if(x <= mid){
            update(idx*2+1, l, mid, x, val);
        } else {
            update(idx*2+2, mid+1, r, x, val);
        }
        segT[idx] = min(segT[idx*2+1], segT[idx*2+2]);
    }
    int getM(int idx, int l, int r, int ql, int qr){
        if(r < ql or l > qr){
            return inf;
        }
        if(r <= qr and l >= ql){
            return segT[idx];
        }
        int mid = (l+r)/2;
        return min(getM(idx*2+1, l, mid, ql, qr), getM(idx*2+2, mid+1, r, ql, qr));
    }
};

segTr s[maxr];

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){
            s[i].init(0, 1, C, W[i]);
        }
        for(int i1=1; i1 <= Q; ++i1)
        {
            ans = inf;
            for(int i = X1[i1]; i <= X2[i1]; ++i){
                ans = min(ans, s[i].getM(0, 1, C, Y1[i1], Y2[i1]));
            }
            if(ans != inf)
            {
                O[i1] = ans;
            } else {
                O[i1] = -1;
            }
        }
        return;
    }
    for(int i1 = 1; i1 <= Q; ++i1)
    {
        es.clear();
        for(int i = 1; i <= N; ++i){
            p[i] = i;
        }
        ans = 0;
        for(int i = X1[i1]; i <= X2[i1]; ++i){
            for(int j = Y1[i1]; j <= Y2[i1]; ++j){
                es.push_back({W[i][j], {U[i][j], V[i][j]}});
            }
        }
        sort(es.begin(), es.end());
        for(auto i : es){
            int u = i.second.first, v = i.second.second;
            // u -> v
            if(join(u, v)){
                ans += i.first;
            }
        }
        int minP = maxn, maxP = 0;
        for(int i = 1 ; i <= N; ++i){
            maxP = max(maxP, findP(i));
            minP = min(minP, findP(i));
        }
        if(maxP == minP){
            O[i1] = ans;
        } else {
            O[i1] = -1;
        }
    }
};