Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m,s;

#define MAXN 100010

struct query{int id,r1,c1,r2,c2;}q[MAXN],q_[MAXN];

int ans[MAXN];

inline int id(int x,int y){return (x - 1) * m + y;}

struct edge{int to,nxt,v;}e[MAXN * 4];

int edgenum = 0,lin[MAXN] = {0};

inline void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

int d[MAXN];

bool vis[MAXN];

priority_queue< pair<int,int> > pq;

#define R register

inline void dijkstra(int s,int r1,int c1,int r2,int c2)

{

	R int delta = d[s];

	for(R int i = r1;i <= r2;++i)for(int j = c1;j <= c2;++j)d[id(i,j)] += delta,vis[id(i,j)] = false;

	pq.push(make_pair(0,s));d[s] = 0;

	while(!pq.empty())

	{

		R int k = pq.top().second;pq.pop();if(vis[k])continue;vis[k] = true;

		for(R int i = lin[k];i != 0;i = e[i].nxt)

			if(d[e[i].to] > d[k] + e[i].v)d[e[i].to] = d[k] + e[i].v,pq.push(make_pair(-d[e[i].to],e[i].to));

	}

	return;

}

void solve(int r1,int c1,int r2,int c2,int l,int r)

{

	if(l > r)return;

	if(r1 == r2 && c1 == c2){for(R int i = l;i <= r;++i)ans[q[i].id] = 0;return;}

	//cout << r1 << " " << c1 << " " << r2 << " " << c2 << " : " << endl;

	//for(int i = l;i <= r;++i)cout << q[i].r1 << " " << q[i].c1 << " " << q[i].r2 << " " << q[i].c2 << endl;

	for(R int i = r1;i <= r2;++i)for(R int j = c1;j <= c2;++j)d[id(i,j)] = 100000000;

	if(r2 - r1 + 1 < c2 - c1 + 1)

	{

		R int mid = (c1 + c2) / 2;

		for(R int i = r1;i <= r2;++i)

		{

			dijkstra(id(i,mid),r1,c1,r2,c2);

			for(R int k = l;k <= r;++k)ans[q[k].id] = min(ans[q[k].id],d[id(q[k].r1,q[k].c1)] + d[id(q[k].r2,q[k].c2)]);

		}

		R int curl = l,curr = r;

		for(R int k = l;k <= r;++k)

		{

			if(q[k].c1 < mid && q[k].c2 < mid)q_[curl++] = q[k];

			if(q[k].c1 > mid && q[k].c2 > mid)q_[curr--] = q[k];

		}

		for(R int k = l;k <= r;++k)q[k] = q_[k];

		solve(r1,c1,r2,mid - 1,l,curl - 1);solve(r1,mid + 1,r2,c2,curr + 1,r);

	}

	else

	{

		R int mid = (r1 + r2) / 2;

		for(R int i = c1;i <= c2;++i)

		{

			dijkstra(id(mid,i),r1,c1,r2,c2);

			for(R int k = l;k <= r;++k)ans[q[k].id] = min(ans[q[k].id],d[id(q[k].r1,q[k].c1)] + d[id(q[k].r2,q[k].c2)]);

		}

		R int curl = l,curr = r;

		for(R int k = l;k <= r;++k)

		{

			if(q[k].r1 < mid && q[k].r2 < mid)q_[curl++] = q[k];

			if(q[k].r1 > mid && q[k].r2 > mid)q_[curr--] = q[k];

		}

		for(R int k = l;k <= r;++k)q[k] = q_[k];

		solve(r1,c1,mid - 1,c2,l,curl - 1);solve(mid + 1,c1,r2,c2,curr + 1,r);

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(R int i = 1;i <= n;++i)for(R int j = 1;j < m;++j)add(id(i,j),id(i,j + 1),rd());

	for(R int i = 1;i < n;++i)for(R int j = 1;j <= m;++j)add(id(i,j),id(i + 1,j),rd());

	scanf("%d",&s);

	for(R int i = 1;i <= s;++i){q[i].r1 = rd();q[i].c1 = rd();q[i].r2 = rd();q[i].c2 = rd();q[i].id = i;}

	memset(ans,0x3f,sizeof(ans));memset(d,0x3f,sizeof(d));

	for(R int i = 1;i <= n;++i)for(R int j = 1;j <= m;++j)vis[id(i,j)] = true;

	solve(1,1,n,m,1,s);

	for(R int i = 1;i <= s;++i)printf("%d\n",ans[i]);

	return 0;

}