#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back bool AAA; const int MAXN=100010,N=40,M=2010,Mod=1e9+7; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;} int n,m; pii q[MAXN]; vector<int>t[MAXN<<2]; ll as[MAXN]; #define nd vector<pair<int,seg>> #define seg vector<pii> seg mrge(seg &x,seg &y){ seg res; for(int i=0,j=0;i<x.size()||j<y.size();){ pii tmp; if(j>=y.size()||i<x.size()&&x[i]<y[j])tmp=x[i],i++; else tmp=y[j],j++; if(res.empty()||res.back().sc<tmp.fr)res.pb(tmp); else res.back().sc=max(res.back().sc,tmp.sc); } return res; } nd mrge(nd &x,nd &y){ nd res={}; seg nowx={},nowy={}; for(int i=0,j=0;i<x.size()||j<y.size();){ int tmp; if(j>=y.size()||i<x.size()&&x[i].fr<y[j].fr)tmp=x[i].fr; else tmp=y[j].fr; if(i<x.size()&&x[i].fr<=tmp)nowx=x[i].sc,i++; if(j<y.size()&&y[j].fr<=tmp)nowy=y[j].sc,j++; seg tp=mrge(nowx,nowy); if(res.empty()||tp!=res.back().sc)res.pb(mk(tmp,tp)); } int cnt=0; for(auto o:res)cnt+=o.sc.size(); return res; } #define lson (pos<<1) #define rson (pos<<1|1) nd p[MAXN],a[MAXN]; void upd(int pos,int l,int r,int ql,int qr,int x){ if(l==r){ t[pos].pb(x); return; } int mid=(l+r)>>1; if(ql<=mid&&qr>mid){t[pos].pb(x);return;} if(qr<=mid)upd(lson,l,mid,ql,qr,x); if(ql>mid)upd(rson,mid+1,r,ql,qr,x); } ll val(nd G){ ll res=0,ls=0,rs=0; for(auto o:G){ if(rs)res+=(ll)(o.fr-ls)*rs; ls=o.fr,rs=0; for(auto e:o.sc)rs+=e.sc-e.fr; } return res; } void calc(int pos,int l,int r){ if(l==r){ if(!t[pos].empty()){ ll s=val(a[l]); for(auto o:t[pos])as[o]=s; } return; } int mid=(l+r)>>1; if(!t[pos].empty()){ p[mid]=a[mid],p[mid+1]=a[mid+1]; for(int i=mid-1;i>=l;i--)p[i]=mrge(p[i+1],a[i]); for(int i=mid+2;i<=r;i++)p[i]=mrge(p[i-1],a[i]); for(auto o:t[pos])as[o]=val(mrge(p[q[o].fr],p[q[o].sc])); } calc(lson,l,mid),calc(rson,mid+1,r); } void slv(){read(); n=read(),m=read(); for(int i=1;i<=n;i++){ int l=read(),d=read(),r=read(),u=read(); a[i]=(nd){mk(l,(seg){mk(d,u)}),mk(r,(seg){})}; } for(int i=1;i<=m;i++){ q[i].fr=read(),q[i].sc=read(); upd(1,1,n,q[i].fr,q[i].sc,i); } calc(1,1,n); for(int i=1;i<=m;i++)printf("%lld\n",as[i]); } bool BBB; signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; // cerr<<((&AAA)-(&BBB))/1024.0/1024<<"MB\n"; return 0; }