#include<bits/stdc++.h> #define ll long long #define mk make_pair #define fi first #define se second using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } const int N=1e5+5; int n,q; struct Rec{ int lx,rx,ly,ry,tim; Rec(int Lx=0,int Rx=0,int Ly=0,int Ry=0,int T=0):lx(Lx),rx(Rx),ly(Ly),ry(Ry),tim(T){} }; Rec Is[N],Js[N]; int ncnt=0; struct BIT{ ll c[N]; int lowbit(int x){return x&(-x);} void add(int x,ll v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;} ll qsum(int x){ll res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;} }T; bool Cap(int l1,int r1,int l2,int r2){ if(l1>l2)swap(l1,l2),swap(r1,r2); return r1>l2; } bool In(int l,int r,int x){return l<=x&&x<=r;} void addrec(int x1,int x2,int y1,int y2,int nw){ // cout<<"addrec x : ["<<x1<<","<<x2<<"] y: ["<<y1<<","<<y2<<"] nw = "<<nw<<endl; // cout<<"Is = ";for(auto [lx,rx,ly,ry,t]:Is)cout<<"(["<<lx<<","<<rx<<"] , ["<<ly<<","<<ry<<"] : "<<t<<") ";puts(""); auto split_x=[&](int p){ int tot=ncnt; for(int i=1;i<=ncnt;i++){ auto [lx,rx,ly,ry,t]=Is[i]; // no intersect if((!Cap(x1,x2,lx,rx))||(!Cap(y1,y2,ly,ry)))continue; else if(lx<p&&p<rx){ Is[i].rx=p; Is[++tot]=Rec(p,rx,ly,ry,t); } } ncnt=tot; }; auto split_y=[&](int p){ int tot=ncnt; for(int i=1;i<=ncnt;i++){ auto [lx,rx,ly,ry,t]=Is[i]; // no intersect if((!Cap(x1,x2,lx,rx))||(!Cap(y1,y2,ly,ry)))continue; else if(ly<p&&p<=ry){ Is[i].ry=p; Is[++tot]=Rec(lx,rx,p,ry,t); } } ncnt=tot; }; split_x(x1),split_x(x2),split_y(y1),split_y(y2); // cout<<"split -> Is = ";for(auto [lx,rx,ly,ry,t]:Is)cout<<"(["<<lx<<","<<rx<<"] , ["<<ly<<","<<ry<<"] : "<<t<<") ";puts(""); int ntot=0; for(int i=1;i<=ncnt;i++){ auto [lx,rx,ly,ry,t]=Is[i]; if((!Cap(x1,x2,lx,rx))||(!Cap(y1,y2,ly,ry))){ Js[++ntot]=Rec(lx,rx,ly,ry,t); } else{ ll ar=1ll*(rx-lx)*(ry-ly); if(t!=0)T.add(t,-ar); } } ncnt=ntot; for(int i=1;i<=ntot;i++)Is[i]=Js[i]; Is[++ncnt]=Rec(x1,x2,y1,y2,nw); T.add(nw,1ll*(x2-x1)*(y2-y1)); // cout<<" -> Is = ";for(auto [lx,rx,ly,ry,t]:Is)cout<<"(["<<lx<<","<<rx<<"] , ["<<ly<<","<<ry<<"] : "<<t<<") ";puts(""); } ll ans[N]; vector<pair<int,int> >ques[N]; int xa[N],xb[N],ya[N],yb[N]; signed main(void){ // freopen("dierti06.in","r",stdin); // freopen("t2-6.out","w",stdout); // double St=clock(); int test_id=read(); n=read(),q=read(); for(int i=1;i<=n;i++)xa[i]=read(),ya[i]=read(),xb[i]=read(),yb[i]=read(); for(int i=1;i<=q;i++){ int l=read(),r=read(); ques[r].emplace_back(mk(l,i)); } int V=5; Is[++ncnt]=Rec(1,V,1,V,0); for(int i=1;i<=n;i++){ addrec(xa[i],xb[i],ya[i],yb[i],i); // cout<<"size = "<<ncnt<<'\n'; for(auto [j,id]:ques[i])ans[id]=T.qsum(i)-T.qsum(j-1); } for(int i=1;i<=q;i++)cout<<ans[i]<<'\n'; // cerr<<"time = "<<clock()-St<<"ms\n"; return 0; }