其实这个题第一反应一定是线段树分治，但是这样反而更难考虑了（实际上是可做的但很难想到），可见即使看上去最贴切的算法也未必能有效果。
考虑这个DS题，没有什么模型的转化，可能用到的无非就是线段树、平衡树和堆。
首先，显然地，将每个商店拆成出现和消失两个事件，然后按时间一次处理。接下来很容易想到二分，于是每次询问的就是[x-mid,x+mid]中是否包含了所有种类的商店。
考虑如何快速回答询问，我们在+inf处先插入所有种类的商店，并记录每个商店的同种类型的前驱（就是上一个同类型的商店在哪里）。
注意到，如果某种商店在[x-mid,x+mid]中没有出现，则必然有(x+mid,+inf)中的所有这种商店的前驱必然都小于x-mid。
问题再次转化为，实时更新每个商店的前驱，以及询问一个后缀最小值。
第一个操作，我们对每种商店都开一个set即可。第二个操作则是线段树基本操作，可能同坐标上有多个值，这个用可删除堆支持即可。
这样复杂度是两个log的，但往往线段树和二分可以合并。如果找到最大的i满足[i,+inf)的最小前驱mn，则mn+i<=2*x。
线段树上二分，于是复杂度就可以做到一个log了。
#include<set>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson ls[x],L,mid
#define rson rs[x],mid+1,R
#define Root rt,0,inf
#define rep(i,l,r) for (int i=(l),_=(r); i<=_; i++)
using namespace std; const int M=,N=M*,inf=0x3f3f3f3f;
multiset<int>S[M];
int n,k,q,m,x,y,l,t,a,b,cnt,tot,id,rt,ans[M],pos[N],ls[N],rs[N],Mn[N];
struct P{ int op,x,t,k; bool operator <(const P &b)const{ return t!=b.t ? t<b.t : op>b.op; } }w[M*];
struct H{
priority_queue<int,vector<int>,greater<int> >Q1,Q2;
int size(){ return Q1.size()-Q2.size(); }
void push(int x){ Q1.push(x); }
void erase(int x){ Q2.push(x); }
int top(){ while (Q2.size() && Q1.top()==Q2.top()) Q1.pop(),Q2.pop(); return Q1.top(); }
}Q[M]; void mdf(int &x,int L,int R,int p,int u,int v){
if (!x) x=++tot;
if (L==R){
if (!pos[x]) pos[x]=++id;
H &q=Q[pos[x]];
if (~u) q.push(u);
if (~v) q.erase(v);
Mn[x]=q.size() ? q.top() : inf;
return;
}
int mid=(L+R)>>;
if (p<=mid) mdf(lson,p,u,v); else mdf(rson,p,u,v);
Mn[x]=min(Mn[ls[x]],Mn[rs[x]]);
} int que(int p){
int L=,R=inf,x=rt,ans=inf;
while (L!=R){
int mid=(L+R)>>,tmp=min(ans,Mn[rs[x]]);
if (p<=mid && tmp+mid>=*p) ans=tmp,R=mid,x=ls[x];
else L=mid+,x=rs[x];
}
return L-p;
} int main(){
freopen("apioa.in","r",stdin);
freopen("apioa.out","w",stdout);
scanf("%d%d%d",&n,&k,&q); Mn[]=inf;
rep(i,,k) S[i].insert(-inf),S[i].insert(inf),mdf(Root,inf,-inf,-);
rep(i,,n) scanf("%d%d%d%d",&x,&t,&a,&b),w[++m]=(P){,x,a,t},w[++m]=(P){-,x,b,t};
rep(i,,q) scanf("%d%d",&l,&y),w[++m]=(P){,l,y,i};
sort(w+,w+m+);
rep(i,,m){
P p=w[i];
if (p.op==){
multiset<int> &s=S[p.k];
multiset<int>::iterator q=s.upper_bound(p.x),r=q--;
mdf(Root,*r,p.x,*q); mdf(Root,p.x,*q,-);
if (s.size()==) cnt++; s.insert(p.x);
}
if (p.op==-){
multiset<int> &s=S[p.k];
s.erase(s.find(p.x));
if (s.size()==) cnt--;
multiset<int>::iterator q=s.upper_bound(p.x),r=q--;
mdf(Root,*r,*q,p.x); mdf(Root,p.x,-,*q);
}
if (p.op==) ans[p.k]=(cnt==k) ? que(p.x) : -;
}
rep(i,,q) printf("%d\n",ans[i]);
return ;
}