#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define pb push_back
using namespace std;
int dsu[105];
int sajz[105];
int n;
void init(int n){
    ff(i,1,n){
        dsu[i] = i;
        sajz[i] = 1;
    }
}
int findpar(int x){
    if(x == dsu[x])return x;
    return dsu[x] = findpar(dsu[x]);
}
void unite(int x, int y){
    int prvi = findpar(x);
    int drugi = findpar(y);
    if(sajz[prvi] > sajz[drugi]){
        dsu[prvi] = drugi;
        sajz[drugi] += sajz[prvi];
    }
    else{
        dsu[drugi] = prvi;
        sajz[prvi] += sajz[drugi];
    }
}
struct edge{
    int x,y;
    int duz;
};

int u[255][255],v[255][255],w[255][255];
vector<edge>grane;
bool cmp(edge a, edge b){
    return a.duz < b.duz;
}
int resi(int x1,int x2, int y1, int y2){
    init(n);
    grane.clear();
    ff(i,x1,x2){
        ff(j,y1,y2){
            grane.pb({u[i][j], v[i][j], w[i][j]});
        }
    }
    sort(grane.begin(), grane.end(), cmp);
    int res = 0;
    for(auto c:grane){
        int tren1,tren2;
        tren1 = c.x;
        tren2 = c.y;
        if(findpar(tren1) == findpar(tren2))continue;
        unite(tren1, tren2);
        res += c.duz;
    }
    ff(i,1,n){
        if(findpar(i) != findpar(1))return -1;
    }
    return res;

}
short mini[255][255][255][3];
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++)
		O[i] = -1;
    n=N;
    ff(i,1,R){
        ff(j,1,C){
            u[i][j] = U[i][j];
            v[i][j] = V[i][j];
            w[i][j] = W[i][j];
        }
    }
    int q=Q;
    int r=R;
    int c=C;
    if(n == 2){
        //cout <<  "ads";
        ff(i,1,r){
            ff(j,1,c){
                int trmin = 65535;
                ff(k,j,c){
                    int pom = w[i][k];
                    //cout << w[i][k] << " ";
                    trmin = min(trmin, pom);
                    mini[i][j][k][0] = trmin;
                    //cout << i << " " << j << " " << k << " " << mini[i][j][k] << endl;
                }
            }
        }
        //cout << endl;
        ff(i,1,q){
            int x1,y1,x2,y2;
            x1 = X1[i];
            x2 = X2[i];
            y1 = Y1[i];
            y2 = Y2[i];
            int res = 65535;
            //cout << y1 << " " << y2 << endl;
            ff(j,x1,x2){
                res = min(res, (int)mini[j][y1][y2][0]);
                //cout << j << "  " << y1 << " " << y2 << " " << mini[j][y1][y2] << endl;
                //cout << res << endl;
            }

            O[i] = res;
            //cout << res << endl;

        }
        return;
    }
    if(n == 3){
        ff(i,1,r){
            ff(j,1,c){
                ff(k,1,c){
                    ff(l,0,2){
                        mini[i][j][k][l] = -1;
                    }
                }
            }
        }
        ff(i,1,r){
            ff(j,1,c){
                int trmin1 = -1;
                int trmin2 = -1;
                int trmin3 = -1;
                ff(k,j,c){
                    int pom = w[i][k];
                    int koji = u[i][k] + v[i][k] - 2;
                    koji %= 3;
                    if(koji == 0){
                        if(trmin1 == -1)trmin1 = pom;
                        trmin1 = min(trmin1, pom);

                    }
                    else if(koji == 1){
                        if(trmin2 == -1)trmin2 = pom;
                        trmin2 = min(trmin2, pom);
                    }
                    else if(koji == 2){
                        if(trmin3 == -1)trmin3 = pom;
                        trmin3 = min(trmin3, pom);
                    }
                    mini[i][j][k][0] = trmin1;
                    mini[i][j][k][1] = trmin2;
                    mini[i][j][k][2] = trmin3;
                     //trmin = min(trmin, pom);

                    //mini[i][j][k][koji] = trmin;
                }
            }
        }
        //cout << endl;
        ff(i,1,q){
            int x1,y1,x2,y2;
            x1 = X1[i];
            x2 = X2[i];
            y1 = Y1[i];
            y2 = Y2[i];
            int p=-1,d=-1,t=-1;
            ff(j,x1,x2){
                int p1 = mini[j][y1][y2][0];
                int d1 = mini[j][y1][y2][1];
                int t1 = mini[j][y1][y2][2];
                if(p == -1){
                    p = p1;
                }


                if(d == -1){
                    d = d1;
                }


                if(t == -1){
                    t = t1;
                }
                if(p1 > -1)p = min(p,p1);
                if(d1 > -1)d = min(d,d1);
                if(t1 > -1)t = min(t,t1);
            }
            int kolko = 0;
            if(p ==-1)kolko++;
            if(d ==-1)kolko++;
            if(t ==-1)kolko++;
            if(kolko >=2){
                O[i] = -1;
                continue;
            }
            int res;
            if(kolko == 0){
                res = p+d+t - max(max(p,d),t);
            }
            else{
                if(p==-1)res = d+t;
                if(d==-1)res = p+t;
                if(t==-1)res = p+d;
            }
            O[i] = res;
        }
        return;

    }
    ff(i,1,q){
        int x1,y1,x2,y2;
        x1 = X1[i];
        x2 = X2[i];
        y1 = Y1[i];
        y2 = Y2[i];
        int pom = resi(x1,x2,y1,y2);
        O[i] = pom;

    }
}