#include<bits/stdc++.h>
#define maxn 255
#define INF 10000000
#define pii pair<int,int>
using namespace std;

int sz[45];
int p[45];

vector<pair<int,pii>>g;

void build(int n)
{
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        p[i]=i;
    }
}
int fnd(int x)
{
    if(x==p[x])return x;
    return p[x]=fnd(p[x]);
}
bool same(int x,int y)
{
    return fnd(x)==fnd(y);
}
void unite(int x,int y)
{
    x=fnd(x);
    y=fnd(y);
    if(sz[x]<sz[y])swap(x,y);
    sz[x]+=sz[y];
    p[y]=x;
}


int minn[maxn][maxn][10][10];
int gg[maxn][maxn];
void build2(int r,int c)
{
    int dr=log2(r);
    int dc=log2(c);
    for(int dx=0;dx<=dr;dx++)
        for(int dy=0;dy<=dc;dy++)
        {
            for(int x=1;x+(1<<dx)-1<=r;x++)
            {
                for(int y=1;y+(1<<dy)-1<=c;y++)
                {
                    if(dx==0 && dy==0)
                    {
                        minn[x][y][dx][dy]=gg[x][y];
                    }
                    else if(dx!=0)
                    {
                        minn[x][y][dx][dy]=min(minn[x][y][dx-1][dy],minn[x+(1<<(dx-1))][y][dx-1][dy]);
                    }
                    else
                    {
                        minn[x][y][dx][dy]=min(minn[x][y][dx][dy-1],minn[x][y+(1<<(dy-1))][dx][dy-1]);
                    }
                }
            }
        }
}
int minnn(int x1,int y1,int x2,int y2)
{
    if(x1>x2)swap(x1,x2);
    if(y1>y2)swap(y1,y2);

    int lx=log2(x2-x1+1);
    int ly=log2(y2-y1+1);

    return min(min(minn[x1][y1][lx][ly],minn[x2-(1<<lx)+1][y1][lx][ly]),min(minn[x1][y2-(1<<ly)+1][lx][ly],minn[x2-(1<<lx)+1][y2-(1<<ly)+1][lx][ly]));
}

int adj[41][41][50005];

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<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            for(int x=1;x<=r;x++)
                for(int y=1;y<=c;y++)
                {
                    int uu=u[x][y];
                    int vv=v[x][y];
                    if(uu>vv)swap(uu,vv);
                    if(uu==i && vv==j)gg[x][y]=w[x][y];
                    else gg[x][y]=INF;
                }

            build2(r,c);
            for(int k=1;k<=q;k++)
            {
                adj[i][j][k]=minnn(x1[k],y1[k],x2[k],y2[k]);
            }
        }

    for(int k=1;k<=q;k++)
    {
        g.clear();
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                //cout<<adj[i][j][k]<<" ";
                if(adj[i][j][k]<INF)
                {
                    g.push_back({adj[i][j][k],{i,j}});
                }
            }
            //cout<<endl;
        }


        sort(g.begin(),g.end());

        build(n);
        o[k]=0;
        int cv=1;
        int len=g.size();
        for(int i=0;i<len;i++)
        {
            int uu=g[i].second.first;
            int vv=g[i].second.second;
            int ww=g[i].first;
            if(!same(uu,vv))
            {
                o[k]+=ww;
                cv++;
                unite(uu,vv);
            }
        }

        if(cv<n)o[k]=-1;
    }
}