#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int INF = 1e9;
int tree[10000];

void update(int node,int left,int right,int idx,int val)
{
    if(left == right)
    {
        tree[node]=min(tree[node],val);
        return ;
    }
    int mid=left+right>>1;
    if(idx <= mid)update(node*2,left,mid,idx,val);
    else update(node*2+1,mid+1,right,idx,val);
    tree[node]=min(tree[node*2],tree[node*2+1]);
}
int query(int node,int left,int right,int l,int r)
{
    if(left > right || left > r || l > right)return INF;
    if(left >= l && right <= r)return tree[node];
    int mid=left+right>>1;
    return min(query(node*2,left,mid,l,r),query(node*2+1,mid+1,right,l,r));
}
void build(int node,int left,int right)
{
    if(left==right)
    {
        tree[node]=INF;
        return ;
    }
    if(left > right)return ;
    int mid=left+right>>1;
    build(node*2,left,mid);
    build(node*2+1,mid+1,right);
    tree[node]=INF;
}

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(R <= 100 && C <= 100 && Q <= 100)
    {
        int n = N;
        for(int q = 1; q <= Q; q++)
        {
            int mat[N+1][N+1];
            int cost[N+1];
            bool bio[N+1];
            for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)mat[i][j]=INF;
            for(int i = 1; i <= n; i++)bio[i]=false;
            for(int i = 1; i <= n; i++)cost[i]=INF;
            for(int x = X1[q]; x <= X2[q]; x++)
            {
                for(int y = Y1[q]; y <= Y2[q]; y++)
                {
                    int u = U[x][y];
                    int v = V[x][y];
                    int w = W[x][y];
                    mat[u][v]=min(mat[u][v],w);
                    mat[v][u]=min(mat[v][u],w);
                }
            }
            cost[1]=0;
            int ans = 0;
            for(int i = 0; i < n; i++)
            {
                int tr=-1;
                for(int j = 1; j <= n; j++)
                {
                    if(bio[j])continue;
                    if(tr==-1||cost[j]<cost[tr])tr=j;
                }
                if(tr==-1)break;
                if(cost[tr]==INF)break;
                ans+=cost[tr];
                bio[tr]=1;
                for(int j = 1; j <= n; j++)
                {
                    if(bio[j])continue;
                    cost[j]=min(cost[j],mat[tr][j]);
                }
            }
            for(int i = 1; i <= n; i++)if(!bio[i])ans=-1;
            O[q]=ans;
        }
        return ;
    }
    else if(N==2)
    {
        vector <int> sve[R+1][R+1];
        for(int i = 1; i <= Q; i++)
        {
            sve[X1[i]][X2[i]].push_back(i);
        }
        for(int i = 1; i <= R; i++)
        {
            //int tree[4*C];
            build(1,1,C);
            for(int j = i; j <= R; j++)
            {
                for(int k = 1; k <= C; k++)
                {
                    update(1,1,C,k,W[j][k]);
                }
                for(auto x:sve[i][j])
                {
                    O[x]=query(1,1,C,Y1[x],Y2[x]);
                }
            }
        }
    }
}