o59_mar_c2_wormholes

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli INF = 1e18;
const int N = 60;
using pi = pair <int, int>;
using pll = pair <lli, lli>;
using pil = pair <int, lli>;
lli dis[N+10][N+10];
bool vs[N+10][N+10];
pll U[N+10], V[N+10];
vector <pll> coor;
vector <int> g[N+10];
int sz;
void Print();

lli Distance(pll u, pll v){
    return abs( u.first - v.first ) + abs( u.second - v.second );
}

int index_coor(lli x, lli y){
    int l = 0, r = sz-1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(coor[mid].first == x and coor[mid].second == y) return mid;
        else if(coor[mid].first < x or (coor[mid].first == x and coor[mid].second < y)) l = mid + 1;
        else r = mid - 1;
    }
}

int main(){

    int m, Q;
    scanf("%d%d", &m, &Q);

    for(int i=1;i<=m;i++){
        lli ux, uy, vx, vy;
        scanf("%lld%lld%lld%lld", &ux, &uy, &vx, &vy);
        U[i] = {ux, uy};
        V[i] = {vx, vy};
        coor.push_back({ux, uy});
        coor.push_back({vx, vy});
    }

    sort(coor.begin(), coor.end());
    coor.resize( unique(coor.begin(), coor.end()) - coor.begin() );
    sz = coor.size();

    for(int i=1;i<=m;i++){
        int idu = index_coor(U[i].first, U[i].second);
        int idv = index_coor(V[i].first, V[i].second);
        g[idu].push_back(idv);
        g[idv].push_back(idu);
    }

    for(int i=0;i<sz;i++){
        for(int j=0;j<sz;j++){
            dis[i][j] = INF;
        }
    }

    for(int i=0;i<sz;i++){
        priority_queue <pil, vector <pil>, greater <pil>> pq;
        pq.push({0, i});
        dis[i][i] = 0;
        while(!pq.empty()){
            int u = pq.top().second;
            lli d = pq.top().first;
            pq.pop();
            if(vs[i][u]) continue;
            vs[i][u] = true;
            for(auto v: g[u]){
                dis[i][v] = d;
                pq.push({dis[i][v], v});
            }
            for(int v=0;v<sz;v++){
                lli dd = Distance(coor[u], coor[v]);
                if(!vs[i][v] and d + dd < dis[i][v]){
                    dis[i][v] = d + dd;
                    pq.push({dis[i][v], v});
                }
            }
        }
    }

    for(int q=1;q<=Q;q++){
        lli x1, x2, y1, y2;
        scanf("%lld%lld%lld%lld", &x1, &x2, &y1, &y2);
        lli ans = Distance({x1, x2}, {y1, y2});
        for(int i=0;i<sz;i++){
            for(int j=i+1;j<sz;j++){
                lli a, b;
                a = Distance(coor[i], {x1, x2});
                b = Distance({y1, y2}, coor[j]);
                ans = min(ans, a + b + dis[i][j]);
                a = Distance(coor[i], {y1, y2});
                b = Distance({x1, x2}, coor[j]);
                ans = min(ans, a + b + dis[i][j]);
            }
        }
        printf("%lld\n", ans);
    }

    return 0;
}

void Print(){
    for(int i=0;i<sz;i++) printf("%d = (%lld , %lld)\n", i, coor[i].first, coor[i].second);
    for(int i=0;i<sz;i++){
        for(auto v: g[i]){
            printf("%d -> %d\n", i, v);
        }
    }
    for(int i=0;i<sz;i++){
        for(int j=0;j<sz;j++){
            printf("%lld ", dis[i][j]);
        }
        printf("\n");
    }
}