题解：AT_abc394_g [ABC394G] Dense Buildings

import sys
sys.setrecursionlimit(1 << 25)

def main():
    input = sys.stdin.read().split()
    ptr = 0
    H = int(input[ptr]); ptr +=1
    W = int(input[ptr]); ptr +=1
    F = []
    for _ in range(H):
        row = list(map(int, input[ptr:ptr+W]))
        ptr += W
        F.append(row)
    Q = int(input[ptr]); ptr +=1
    queries = []
    for _ in range(Q):
        A = int(input[ptr])-1; ptr +=1
        B = int(input[ptr])-1; ptr +=1
        Y = int(input[ptr]); ptr +=1
        C = int(input[ptr])-1; ptr +=1
        D = int(input[ptr])-1; ptr +=1
        Z = int(input[ptr]); ptr +=1
        queries.append( (A,B,Y,C,D,Z) )

    edges = []
    for i in range(H):
        for j in range(W):
            if i+1 < H:
                w = min(F[i][j], F[i+1][j])
                edges.append( ( -w, i*W+j, (i+1)*W+j ) )
            if j+1 < W:
                w = min(F[i][j], F[i][j+1])
                edges.append( ( -w, i*W+j, i*W+(j+1) ) )

    edges.sort()
    parent = list(range(H*W))
    rank = [1]*(H*W)
    parent_edge = [ -1 ]*(H*W)
    mst_edges = [[] for _ in range(H*W)]

    def find(u):
        while parent[u] != u:
            u = parent[u]
        return u

    for edge in edges:
        w_neg, u, v = edge
        w = -w_neg
        ru = find(u)
        rv = find(v)
        if ru != rv:
            if rank[ru] < rank[rv]:
                ru, rv = rv, ru
                u, v = v, u
            parent[rv] = ru
            if rank[ru] == rank[rv]:
                rank[ru] +=1
            mst_edges[u].append( (v, w) )
            mst_edges[v].append( (u, w) )
            parent_edge[v] = (u, w)
            parent_edge[u] = (v, w)

    LOG = 20
    up = [ [ -1 for _ in range(LOG) ] for __ in range(H*W) ]
    min_edge = [ [ 0 for _ in range(LOG) ] for __ in range(H*W) ]
    depth = [0]*(H*W)

    from collections import deque
    visited = [False]*(H*W)
    for root in range(H*W):
        if visited[root]:
            continue
        q = deque()
        q.append( (root, -1, 0) )
        visited[root] = True
        while q:
            u, p_u, d = q.popleft()
            up[u][0] = p_u
            depth[u] = d
            if p_u != -1:
                for (v, w) in mst_edges[u]:
                    if v == p_u:
                        min_edge[u][0] = w
                        break
            else:
                min_edge[u][0] = 0
            for k in range(1, LOG):
                if up[u][k-1] == -1:
                    up[u][k] = -1
                    min_edge[u][k] = 0
                else:
                    up[u][k] = up[ up[u][k-1] ][k-1]
                    min_edge[u][k] = min( min_edge[u][k-1], min_edge[ up[u][k-1] ][k-1] )
            for (v, w) in mst_edges[u]:
                if not visited[v]:
                    visited[v] = True
                    q.append( (v, u, d+1) )

    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        min_val = float('inf')
        for k in reversed(range(LOG)):
            if depth[u] - (1 << k) >= depth[v]:
                min_val = min( min_val, min_edge[u][k] )
                u = up[u][k]
        if u == v:
            return (u, min_val)
        for k in reversed(range(LOG)):
            if up[u][k] != -1 and up[u][k] != up[v][k]:
                min_val = min( min_val, min_edge[u][k], min_edge[v][k] )
                u = up[u][k]
                v = up[v][k]
        min_val = min( min_val, min_edge[u][0], min_edge[v][0] )
        return (up[u][0], min_val)

    def get_min_edge(u, v):
        l, min_val = lca(u, v)
        return min_val

    for q in queries:
        A,B,Y,C,D,Z = q
        u = A * W + B
        v = C * W + D
        if u == v:
            print( abs(Y - Z) )
            continue
        X_max = get_min_edge(u, v)
        X_opt = min( X_max, Y, Z )
        res = abs(Y - X_opt) + abs(Z - X_opt)
        print(res)

if __name__ == '__main__':
    main()