#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, 10> get_array10(int V) { return array<int, 10>{V,V,V,V,V,V,V,V,V,V}; } inline array<array<int,10>, 10> get_array10(array<int,10> V) { return array<array<int,10>, 10>{V,V,V,V,V,V,V,V,V,V}; } inline array<int, 20> get_array20(int V) { return array<int, 20>{V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V,V}; } inline array<array<int,20>, 20> get_array20(array<int,20> V) { return array<array<int,20>, 20>{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,10>a[100005],b[100005]; array<array<int,10>,10>l[100005],r[100005]; void floyd(array<array<int,10>,10>const&d1,array<array<int,10>,10>&d2,array<int,10>const&d3){ array<array<int,20>,20>dis=get_array20(get_array20(inf)); for(int i=0;i<m;i++)for(int j=0;j<m;j++)dis[i][j]=d1[i][j]; for(int i=0;i<m;i++)for(int j=0;j<m;j++)dis[i+m][j+m]=d2[i][j]; for(int i=0;i<m;i++)dis[i][i+m]=dis[i+m][i]=d3[i]; for(int k=0;k<m+m;k++){ for(int i=0;i<m+m;i++)for(int j=0;j<m+m;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[j][k]); } for(int i=0;i<m;i++)for(int j=0;j<m;j++)d2[i][j]=dis[i+m][j+m]; } struct node{ int l,r; array<array<int,10>,10>dis; friend node operator+(node const&x,node const&y){ node res={x.l,y.r}; res.dis=get_array10(get_array10(inf)); for(int i=0;i<m;i++){ for(int k=0;k<m;k++){ for(int j=0;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,10> operator+(array<int,10> const&x,node const&y){ array<int,10> res=get_array10(inf); for(int i=0;i<m;i++)for(int j=0;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,10>&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=0;i<m;i++)for(int j=1;j<n;j++)read(a[j][i]); for(int i=0;i<m-1;i++)for(int j=1;j<=n;j++)read(b[j][i]); for(int i=1;i<=n;i++){ for(int j=0;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=0;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_array10(0)); } bd(1,n,1); while(q--){ int a,b,c,d; read(a,b,c,d); a--,c--; if(b>d)swap(a,c),swap(b,d); array<int,10>ans=get_array10(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; }