#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
struct Compress
{
vector<int> id;
void Add(int x){ id.pb(x);}
void Build(){ sort(id.begin(),id.end());id.erase(unique(id.begin(),id.end()),id.end());}
int GetL(int x){ return lower_bound(id.begin(),id.end(),x)-id.begin()+1;}
int GetR(int x){ return upper_bound(id.begin(),id.end(),x)-id.begin();}
int Val(int x){ return id[x-1];}
int size(){ return id.size();}
} TME,LOC;
const int N=300050;
const int M=2*N;
const int K=2*M;
const int inf=1e9+7;
struct SegmentTree
{
multiset<int> val[K];
int ls[K],rs[K],tsz,root;
string name;
SegmentTree(){}
void SetName(string s){ name=s;}
void Add(int &c, int ss, int se, int qs, int qe, int f, int t)
{
if(qs>qe || qs>se || ss>qe) return;
if(!c) c=++tsz;
if(qs<=ss && qe>=se)
{
if(t==1) val[c].insert(f);
else
{
//if(!val[c].count(f)) printf("???\n");
val[c].erase(val[c].find(f));
}
return;
}
int mid=ss+se>>1;
Add(ls[c],ss,mid,qs,qe,f,t);
Add(rs[c],mid+1,se,qs,qe,f,t);
}
void Add(int qs, int qe, int f)
{
//cout<<name<<":Add: ("<<qs<<", "<<qe<<") "<<f<<"\n";
Add(root,1,M,qs,qe,f,1);
}
void Del(int qs, int qe, int f)
{
//cout<<name<<":Del: ("<<qs<<", "<<qe<<") "<<f<<"\n";
Add(root,1,M,qs,qe,f,0);
}
int Get(int c, int ss, int se, int qi)
{
int ans=val[c].size()?*val[c].rbegin():-inf;
if(ss==se) return ans;
int mid=ss+se>>1;
if(qi<=mid) ans=max(ans,Get(ls[c],ss,mid,qi));
else ans=max(ans,Get(rs[c],mid+1,se,qi));
return ans;
}
int Get(int qi){ return Get(root,1,M,qi);}
} LST,RST;
int x[N],t[N],l[N],r[N],qx[N],qy[N],ans[N],k,active;
vector<int> QS[M],L[M],R[M];
set<pair<int,int>> all[N];
void Add(int i)
{
all[t[i]].insert(mp(x[i],i));
auto it=all[t[i]].find(mp(x[i],i));
bool lf=0,rf=0;
int lid,rid;
if(it!=all[t[i]].begin()) it--,lid=it->second,lf=1,it++;
it++;if(it!=all[t[i]].end()) rid=it->second,rf=1;it--;
if(lf && rf)
{
int mid=LOC.Val(x[lid])+LOC.Val(x[rid])>>1;
LST.Del(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
RST.Del(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
LST.Add(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
RST.Add(LOC.GetL(mid+1),x[i],LOC.Val(x[i]));
mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
LST.Add(x[i],LOC.GetR(mid),-LOC.Val(x[i]));
RST.Add(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
}
else if(lf)
{
LST.Del(x[lid],LOC.size(),-LOC.Val(x[lid]));
LST.Add(x[i],LOC.size(),-LOC.Val(x[i]));
int mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
LST.Add(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
RST.Add(LOC.GetL(mid+1),x[i],LOC.Val(x[i]));
}
else if(rf)
{
RST.Del(1,x[rid],LOC.Val(x[rid]));
RST.Add(1,x[i],LOC.Val(x[i]));
int mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
LST.Add(x[i],LOC.GetR(mid),-LOC.Val(x[i]));
RST.Add(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
}
else
{
LST.Add(x[i],LOC.size(),-LOC.Val(x[i]));
RST.Add(1,x[i],LOC.Val(x[i]));
}
if(all[t[i]].size()==1) active++;
}
void Del(int i)
{
auto it=all[t[i]].find(mp(x[i],i));
bool lf=0,rf=0;
int lid,rid;
if(it!=all[t[i]].begin()) it--,lid=it->second,lf=1,it++;
it++;if(it!=all[t[i]].end()) rid=it->second,rf=1;it--;
if(lf && rf)
{
int mid=LOC.Val(x[lid])+LOC.Val(x[rid])>>1;
LST.Add(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
RST.Add(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
LST.Del(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
RST.Del(LOC.GetL(mid+1),x[i],LOC.Val(x[i]));
mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
LST.Del(x[i],LOC.GetR(mid),-LOC.Val(x[i]));
RST.Del(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
}
else if(lf)
{
LST.Add(x[lid],LOC.size(),-LOC.Val(x[lid]));
LST.Del(x[i],LOC.size(),-LOC.Val(x[i]));
int mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
LST.Del(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
RST.Del(LOC.GetL(mid+1),x[i],LOC.Val(x[i]));
}
else if(rf)
{
RST.Add(1,x[rid],LOC.Val(x[rid]));
RST.Del(1,x[i],LOC.Val(x[i]));
int mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
LST.Del(x[i],LOC.GetR(mid),-LOC.Val(x[i]));
RST.Del(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
}
else
{
LST.Del(x[i],LOC.size(),-LOC.Val(x[i]));
RST.Del(1,x[i],LOC.Val(x[i]));
}
if(all[t[i]].size()==1) active--;
all[t[i]].erase(mp(x[i],i));
}
int Get(int i)
{
if(active!=k) return -1;
int ans=max(LST.Get(qx[i])+LOC.Val(qx[i]),RST.Get(qx[i])-LOC.Val(qx[i]));
//printf("%i %i %i\n",LST.Get(qx[i])+LOC.Val(qx[i]),RST.Get(qx[i])-LOC.Val(qx[i]),ans);
return ans;
}
void Solve(int ss, int se, vector<int> work)
{
for(int i:work) L[l[i]].pb(i),R[r[i]].pb(i);
for(int i=ss;i<=se;i++)
{
for(int j:L[i]) Add(j);
for(int j:QS[i]) ans[j]=Get(j);
for(int j:R[i]) Del(j);
}
}
int main()
{
LST.SetName("LST");
RST.SetName("RST");
int n,q;
scanf("%i %i %i",&n,&k,&q);
for(int i=1;i<=n;i++)
{
scanf("%i %i %i %i",&x[i],&t[i],&l[i],&r[i]);
TME.Add(l[i]);
TME.Add(r[i]);
LOC.Add(x[i]);
}
for(int i=1;i<=q;i++)
{
scanf("%i %i",&qx[i],&qy[i]);
TME.Add(qy[i]);
LOC.Add(qx[i]);
}
TME.Build();
LOC.Build();
for(int i=1;i<=n;i++)
{
l[i]=TME.GetL(l[i]);
r[i]=TME.GetL(r[i]);
x[i]=LOC.GetL(x[i]);
}
for(int i=1;i<=q;i++)
{
qy[i]=TME.GetL(qy[i]);
qx[i]=LOC.GetL(qx[i]);
QS[qy[i]].pb(i);
}
vector<int> work(n);
for(int i=1;i<=n;i++) work[i-1]=i;
Solve(1,TME.size(),work);
for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
return 0;
}
