#include<bits/stdc++.h> #define int long long #define y0 jp8akioi #define y1 jbhakioi #define yn baka24akioi #define fls fflush(stdout) using namespace std; inline void read(int &x){ x=0;char c=getchar();bool neg=0; for(;!isdigit(c);c=getchar())neg=(c=='-'); for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48); if(neg)x=-x; } inline void read(string &x){ x="";char c=getchar(); for(;isspace(c);c=getchar()); for(;!isspace(c)&&c!=EOF;c=getchar())x+=c; } inline void read(char &x){ x=getchar(); while(isspace(x))x=getchar(); } template<typename... T> inline void read(T&... x){ (read(x),...); } constexpr int inf=1e18; inline array<int, 11> get_array11(int V) { return array<int, 11>{V,V,V,V,V,V,V,V,V,V,V}; } inline array<array<int,11>, 11> get_array11(array<int,11> V) { return array<array<int,11>, 11>{V,V,V,V,V,V,V,V,V,V,V}; } inline array<int, 21> get_array21(int V) { return array<int, 21>{V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V}; } inline array<array<int,21>, 21> get_array21(array<int,21> V) { return array<array<int,21>, 21>{V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V}; } int m,n,q; array<int,11>a[100005],b[100005]; array<array<int,11>,11>l[100005],r[100005]; void floyd(array<array<int,11>,11>const&d1,array<array<int,11>,11>&d2,array<int,11>const&d3){ array<array<int,21>,21>dis=get_array21(get_array21(inf)); for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)dis[i][j]=d1[i][j]; for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)dis[i+m][j+m]=d2[i][j]; for(int i=1;i<=m;i++)dis[i][i+m]=dis[i+m][i]=d3[i]; for(int k=1;k<=m+m;k++){ for(int i=1;i<=m+m;i++)for(int j=1;j<=m+m;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[j][k]); } for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)d2[i][j]=dis[i+m][j+m]; } struct node{ int l,r; array<array<int,11>,11>dis; friend node operator+(node const&x,node const&y){ node res={x.l,y.r}; res.dis=get_array11(get_array11(inf)); for(int i=1;i<=m;i++){ for(int k=1;k<=m;k++){ for(int j=1;j<=m;j++){ res.dis[i][j]=min(x.dis[i][k]+y.dis[k][j]+a[x.r][k],res.dis[i][j]); } } } return res; } friend array<int,11> operator+(array<int,11> const&x,node const&y){ array<int,11> res=get_array11(inf); for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)res[j]=min(res[j],x[i]+y.dis[i][j]+a[y.l-1][i]); return res; } }; node t[400005]; #define ls (p<<1) #define rs (p<<1|1) #define mid (l+r>>1) void bd(int l,int r,int p){ if(l==r){ t[p]={l,r,::r[l]}; return; } bd(l,mid,ls); bd(mid+1,r,rs); t[p]=t[ls]+t[rs]; } void qu(int l,int r,int ml,int mr,array<int,11>&res,int p){ if(ml<=l&&r<=mr){res=res+t[p];return;} if(mid>=ml)qu(l,mid,ml,mr,res,ls); if(mid<mr)qu(mid+1,r,ml,mr,res,rs); } void slv(){ read(m,n,q); for(int i=1;i<=m;i++)for(int j=1;j<n;j++)read(a[j][i]); for(int i=1;i<m;i++)for(int j=1;j<=n;j++)read(b[j][i]); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)for(int k=j+1;k<=m;k++){ l[i][j][k]=l[i][k][j]=l[i][j][k-1]+b[i][k-1]; } if(i>1)floyd(l[i-1],l[i],a[i-1]); } for(int i=n;i>=1;i--){ for(int j=1;j<=m;j++)for(int k=j+1;k<=m;k++){ r[i][j][k]=r[i][k][j]=r[i][j][k-1]+b[i][k-1]; } if(i<n)floyd(l[i+1],l[i],a[i]); } for(int i=1;i<=n;i++){ floyd(l[i],r[i],get_array11(0)); } bd(1,n,1); while(q--){ int a,b,c,d; read(a,b,c,d); if(b>d)swap(a,c),swap(b,d); array<int,11>ans=get_array11(inf); ans[a]=-::a[b-1][a]; qu(1,n,b,d,ans,1); printf("%lld\n",ans[c]); } } signed main(){ // int T;read(T);while(T--) slv(); return 0; }