#include<bits/stdc++.h>
using namespace std;
int x[300005],t[300005],a[300005],b[300005],pp[300005];
int aa[600005],ans[300005],rt[300005];
pair<int,int>pi[300005];
vector<int>r1[600005],r2[600005];
vector<pair<int,int>>wz[600005];
set<int>se[300005];
int rr[300005],an[300005];
int sm[1200005];
int n,k,q;
int cz[300005];
void build(int l,int r,int o){
	if(l==r){
		if(cz[l])sm[o]=rr[l];
		else sm[o]=n+1;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,o<<1);
	build(mid+1,r,o<<1|1);
	sm[o]=min(sm[o<<1],sm[o<<1|1]);
}
void add(int l,int r,int o,int x,int y){
	if(l==r){
		if(cz[x])sm[o]=y;
		else sm[o]=n+1;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)add(l,mid,o<<1,x,y);
	else add(mid+1,r,o<<1|1,x,y);
	sm[o]=min(sm[o<<1],sm[o<<1|1]);
}
int query(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr)return sm[o];
	int mid=(l+r)>>1,ans=INT_MAX;
	if(mid>=ll)ans=min(ans,query(l,mid,o<<1,ll,rr));
	if(mid<rr)ans=min(ans,query(mid+1,r,o<<1|1,ll,rr));
	return ans;
}
void gai(int x,int y){
	if(!cz[x])cz[x]=1;
	add(1,n,1,x,y);
}
void unmo(int x){
	cz[x]=0;add(1,n,1,x,0);
}
int main(){
	scanf("%d%d%d",&n,&k,&q);
	int tt=0;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d%d",&x[i],&t[i],&a[i],&b[i]);
		aa[++tt]=a[i],aa[++tt]=b[i]+1;
		pi[i]=make_pair(x[i],i);
	}
	sort(pi+1,pi+n+1);
	for(int i=1;i<=n;++i){
		rt[i]=t[pi[i].second];
		pp[pi[i].second]=i;
	}
	for(int i=1;i<=n;++i)t[i]=rt[i];
	sort(aa+1,aa+tt+1);
	tt=unique(aa+1,aa+tt+1)-aa-1;
	for(int i=1;i<=n;++i){
		int z1=lower_bound(aa+1,aa+tt+1,a[i])-aa;
		int z2=lower_bound(aa+1,aa+tt+1,b[i]+1)-aa;
		r1[z1].emplace_back(pp[i]);
		r2[z2].emplace_back(pp[i]);
	}
	for(int i=1;i<=q;++i){
		int l,y;
		scanf("%d%d",&l,&y);
		int wy=upper_bound(aa+1,aa+tt+1,y)-aa-1;
		if(!wy||wy==tt){
			ans[i]=-1;
			continue;
		}
		wz[wy].emplace_back(l,i);
	}
	pi[n+1].first=1e9;
	set<int>ss;
	for(int i=1;i<=n;++i)rr[i]=0,cz[i]=0;
	build(1,n,1);
	for(int i=1;i<tt;++i){
		for(auto cu:r2[i]){
			ss.erase(an[t[cu]]);
			auto it=se[t[cu]].find(cu);
			se[t[cu]].erase(it++);
			if(it==se[t[cu]].end())an[t[cu]]=rr[cu];
			else gai(*it,rr[cu]),rr[*it]=rr[cu];
			unmo(cu);rr[cu]=0;
			if(an[t[cu]])ss.emplace(an[t[cu]]);
		}
		for(auto cu:r1[i]){
			if(an[t[cu]])ss.erase(an[t[cu]]);
			auto it=se[t[cu]].emplace(cu).first;
			auto ti=it;++ti;
			rr[cu]=(ti==se[t[cu]].end()?rr[*ti]:an[t[cu]]);
			gai(cu,rr[cu]);
			if(ti==se[t[cu]].end())an[t[cu]]=cu;
			else gai(*ti,cu),rr[*ti]=cu;
			ss.emplace(an[t[cu]]);
		}
		for(auto pii:wz[i]){
			if((signed)ss.size()<k){
				ans[pii.second]=-1;
				continue;
			}
			int l=pii.first;
			int L=0,R=1e8;
			auto it=ss.end();--it;
			int mn=*it;
			while(L<=R){
				int mid=(L+R)>>1;
				int wz=upper_bound(pi+1,pi+n+1,make_pair(l+mid,n))-pi;
				int qz=(wz>n?n+1:query(1,n,1,wz,n));
				int fl=1;
				if(!qz)fl=0;
				else if(min(pi[qz].first,mn)<l-mid)fl=0;
				if(!fl)L=mid+1;
				else R=mid-1;
			}
			ans[pii.second]=L;
		}
	}
	for(int i=1;i<=q;++i)printf("%d\n",ans[i]);
	return 0;
}