#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define lc(x) ((x) << 1) #define rc(x) ((x) << 1 | 1) //#define double long double #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) int a[21][200300]; struct node{ int x,y,w; }; vector<node>T; int l[200300],r[200300]; bool ins[200200]; inline bool cmp(node A,node B){ return A.w>B.w; } inline int ff(int *f,int x){ return f[x]==x?x:f[x]=ff(f[x]); } int A,B,C; inline int F(int x){ return A^(B*x+C); } int n,k,q; int A,B,C; set<pii>S; struct OP{ int l,r,w; }; vector<OP>O[50030]; inline void mod(int xl,int xr,int yl,int yr,int w){ O[yl].push_back({xl,xr,w}); O[yr+1].push_back({xl,xr,-w}); } inline void mod(int l,int r,int w){ int lstx=l; int lsty=p2(*prev(S.lower_bound({l,-1}))); auto it=S.lower_bound({l,-1}); while(it!=S.end()){ int x=p1(*it); int y=p2(*it); mod(lstx,x-1,lsty,r,w); lstx=x; lsty=y+1; if(y>=r)break; S.erase(it); it++; } S.insert({l,r}); } struct node{ int a,b; friend node operator +(const node A,const node B){ return {A.a+B.a,A.b+B.b}; } friend node operator *(const node A,const int x){ return {A.a*x,A.b*x}; } friend node operator *(const int x,const node A){ return {A.a*x,A.b*x}; } inline int f(int x){return a*x+b;} }w[50030<<2],tg[50030<<2]; inline void pd(int x,int l,int r){ int mid=l+r>>1; w[lc(x)]=w[lc(x)]+tg[x]*(mid-l+1); w[rc(x)]=w[rc(x)]+tg[x]*(r-mid); tg[lc(x)]=tg[lc(x)]+tg[x]; tg[rc(x)]=tg[rc(x)]+tg[x]; tg[x]={0,0}; } inline void upd(int x){ w[x]=w[lc(x)]+w[rc(x)]; } inline void mod(int x,int l,int r,int L,int R,node A){ if(L>R)return ; if(L<=l&&r<=R){ tg[x]=tg[x]+A; w[x]=w[x]+A*(r-l+1); return ; } pd(x,l,r); int mid=l+r>>1; if(L<=mid)mod(lc(x),l,mid,L,R,A); if(R>mid)mod(rc(x),mid+1,r,L,R,A); upd(x); } inline node g(int x,int l,int r,int L,int R){ if(L>R)return {0,0}; if(L<=l&&r<=R)return w[x]; pd(x,l,r); int mid=l+r>>1; node res={0,0}; if(L<=mid)res=res+g(lc(x),l,mid,L,R); if(R>mid)res=res+g(rc(x),mid+1,r,L,R); return res; } struct ASK{ int l,id; }; vector<ASK>A[50030]; int ANS[50030]; signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); // freopen("s4.in","r",stdin); // freopen("avatar.in", "r", stdin); // freopen("avatar.out", "w", stdout); cin>>k>>n>>q; for(int i=0;i<=n+1;i++) S.insert({i,i-1}); for(int i=1;i<=k;i++) for(int j=1;j<=n;j++){ cin>>a[i][j]; T.push_back({i,j,a[i][j]}); } sort(T.begin(),T.end(),cmp); for(int i=1;i<=n;i++) l[i]=r[i]=i; for(node A:T) if(!ins[A.y]){ if(ins[A.y-1]) l[A.y]=ff(l,A.y-1); if(ins[A.y+1]) r[A.y]=ff(r,A.y+1); mod(l[A.y],r[A.y],F(A[i].w)); } for(int i=1;i<=q;i++){ int l,r; cin>>l>>r; A[r].push_back({l,i}); } for(int i=1;i<=n;i++){ for(OP e:O[i]) mod(1,1,n,e.l,e.r,{e.w,e.w*(i-1)}); for(ASK a:A) ANS[a.id]=g(1,1,n,a.l,i).f(i); } for(int i=1;i<=q;i++) cout<<ANS[i]<<endl; cout.flush(); return 0; }