#include <queue> #include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int read() { int x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const int MAX = 200033; const int inf = 100000000; #define id(i, j) ((i - 1) * m + (j)) int n, m, cnte, Q, cntid; int invx[20033], invy[20033]; int fir[20033]; struct Query { int x, y, xx, yy, id; } q[100033], tmp[100033]; struct edge { int to, nxt, w; edge() {} edge(int a, int b, int c) { to = a, nxt = b, w = c; } } e[200033]; void addedge(int u, int v, int w) { e[++cnte] = edge(v, fir[u], w), fir[u] = cnte; e[++cnte] = edge(u, fir[v], w), fir[v] = cnte; } int ans[100033], dis[20033]; int que[2000033]; bool inq[20033]; void dijkstra(int s, int xl, int xr, int yl, int yr, int h) { int d = dis[s]; for (int i = xl; i <= xr; i++) for (int j = yl; j <= yr; j++) dis[id(i, j)] = h ? dis[id(i, j)] + d : inf; dis[s] = 0; inq[s] = 1; int l = 10000, r = 10000; que[r++] = s; while (l != r) { int u = que[l++]; inq[u] = 0; for (int i = fir[u]; i; i = e[i].nxt) { int v = e[i].to; int vy = invy[v], vx = invx[v]; if (vx >= xl && vx <= xr && vy >= yl && vy <= yr) if (dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; if (!inq[v]) { if (dis[v] <= dis[que[l]]) que[--l] = v; else que[r++] = v; inq[v] = 1; } } } } } void solve(int xl, int xr, int yl, int yr, int ql, int qr) { if (ql > qr) return; if (xr - xl > yr - yl) { int mid = (xl + xr) >> 1; for (int i = yl; i <= yr; i++) { dijkstra(id(mid, i), xl, xr, yl, yr, i - yl); for (int j = ql; j <= qr; j++) ans[q[j].id] = min(ans[q[j].id], dis[id(q[j].x, q[j].y)] + dis[id(q[j].xx, q[j].yy)]); } int l = ql - 1, r = qr + 1; for (int i = ql; i <= qr; i++) { if (q[i].x < mid && q[i].xx < mid) tmp[++l] = q[i]; else if (q[i].x > mid && q[i].xx > mid) tmp[--r] = q[i]; } for (int i = ql; i <= l; i++) q[i] = tmp[i]; for (int i = r; i <= qr; i++) q[i] = tmp[i]; solve(xl, mid - 1, yl, yr, ql, l); solve(mid + 1, xr, yl, yr, r, qr); } else { int mid = (yl + yr) >> 1; for (int i = xl; i <= xr; i++) { dijkstra(id(i, mid), xl, xr, yl, yr, i - xl); for (int j = ql; j <= qr; j++) ans[q[j].id] = min(ans[q[j].id], dis[id(q[j].x, q[j].y)] + dis[id(q[j].xx, q[j].yy)]); } int l = ql - 1, r = qr + 1; for (int i = ql; i <= qr; i++) { if (q[i].y < mid && q[i].yy < mid) tmp[++l] = q[i]; else if (q[i].y > mid && q[i].yy > mid) tmp[--r] = q[i]; } for (int i = ql; i <= l; i++) q[i] = tmp[i]; for (int i = r; i <= qr; i++) q[i] = tmp[i]; solve(xl, xr, yl, mid - 1, ql, l); solve(xl, xr, mid + 1, yr, r, qr); } } int main() { memset(ans, 63, sizeof ans); n = read(), m = read(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cntid++; invx[cntid] = i, invy[cntid] = j; } for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) addedge(id(i, j), id(i, j + 1), read()); for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++) addedge(id(i, j), id(i + 1, j), read()); Q = read(); for (int i = 1; i <= Q; i++) { q[i].x = read(), q[i].y = read(); q[i].xx = read(), q[i].yy = read(); q[i].id = i; } solve(1, n, 1, m, 1, Q); for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]); return 0; }