M - Mountaineers （MST+树上倍增）

将原图中点每个点四连通方向的点建边，权值为两点权值中较大者的值。对这个图建立最小生成树，那么最小生成树上任意两点之间路径上的最大点权即为答案（因为是树，所以任意两点间的简单路径唯一）通过树上倍增维护维护树上区间最值求出最大值即可。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
#define sz(x) x.size()
#define lbt(x) (x)&(-x)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef pair<int, int> PII;
typedef array<int, 3>ARR;
typedef double db;
const int N = 5e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f;
const db EPS = 1e-9;
int f[N][24], mx[N][24], a[510][510], p[N], w[N], dep[N];
int n, m, q;
vector<array<int, 3>>edg;
vector<int>g[N];
int find(int x) {
    if (x != p[x])p[x] = find(p[x]);
    return p[x];
}
int hs(int x, int y) {
    return (x - 1) * m + y;
}
void dfs(int u, int fa) {
    if (dep[u] != -1)return;
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    mx[u][0] = max(w[u], w[fa]);
    for (int i = 1;i <= 20;i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
        mx[u][i] = max(mx[u][i - 1], mx[f[u][i - 1]][i - 1]);
    }
    for (auto t : g[u]) {
        if (t == fa)continue;
        dfs(t, u);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y])swap(x, y);
    int z = dep[x] - dep[y];
    int res = max(w[x], w[y]);
    for (int i = 0;i <= 20 && z; i++) {
        if (z & 1) {
            res = max(res, mx[x][i]);
            // cout << x / m + 1 << " " << x % m << " " << res << endl;
            x = f[x][i];
        }
        z >>= 1;
    }
    // cout << x << " " << y << endl;
    if (x == y) return res;
    for (int i = 20;i >= 0;i--) {
        if (f[x][i] != f[y][i]) {
            res = max({ res , mx[x][i],mx[y][i] });
            x = f[x][i], y = f[y][i];
        }
    }
    return max(res, mx[x][0]);
}


void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i < N;i++)p[i] = i, dep[i] = -1;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            cin >> a[i][j];
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            w[hs(i, j)] = a[i][j];
            if (i > 1)edg.push_back({ hs(i - 1, j), hs(i,j) ,max(a[i][j],a[i - 1][j]) });
            if (j < m)edg.push_back({ hs(i,j), hs(i,j + 1),max(a[i][j],a[i][j + 1]) });
        }
    }
    sort(all(edg), [&](ARR a, ARR b) {
        return a[2] < b[2];
        });
    for (auto t : edg) {
        int x = t[0], y = t[1];
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            p[fx] = p[fy];
            g[x].push_back(y);
            g[y].push_back(x);
        }
    }
    dfs(1, 0);
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << lca(hs(a, b), hs(c, d)) << endl;
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _ ;
    while (_--)
        solve();
    return 0;
}