//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
int n,k,q;
int ans[300001];
set<int> pre[300001];
map<int,int> pre2[300001];
bool vis[3000001];
map<pair<int,pair<int,int>>,int> xx;
map<pair<int,pair<int,int>>,int> xx2;
map<int,int> ss;
map<int,int> ss2;
map<int,int> ss3;
map<int,int> ss4;
vector<pair<int,int>> yy;
int ne=0;
int nn;
pair<int,int> solve(int i,int j){
pair<int,int> ac={i,0};
pair<int,int> ac2={j+1,0};
return {lower_bound(yy.begin(),yy.end(),ac)-yy.begin(),lower_bound(yy.begin(),yy.end(),ac2)-yy.begin()-1};
}
priority_queue<pair<int,int>> tree[4*400001];
priority_queue<pair<int,int>> tree2[4*400001];
int tree3[4*800001][2];
int kk=1;
//int ans[300001];
void update(int no,int l,int r,int aa,int bb,pair<int,int> x,int st){
/*if(no==0){
cout<<aa<<":"<<bb<<":"<<x.a<<":"<<x.b<<endl;
}*/
if(r<aa or l>bb or aa>bb){
return;
}
if(aa<=l and r<=bb){
//cout<<l<<",,"<<r<<endl;
tree[no].push(x);
tree2[no].push({-x.a,x.b});
}
else{
int mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,x,st);
update(no*2+2,mid+1,r,aa,bb,x,st);
}
}
void update2(int no,int l,int r,int aa,int bb,int x,int st){
/* if(no==0){
cout<<aa<<":"<<bb<<":"<<x<<endl;
}*/
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
//cout<<l<<",,"<<r<<endl;
tree3[no][0]=min(tree3[no][0],x);
tree3[no][1]=max(tree3[no][1],x);
/* if(kk){
if(tree[no].size()){
pair<int,int> ma=tree[no].top();
tree[no].pop();
tree[no].push(max(ma,x));
ma=tree2[no].top();
tree2[no].pop();
tree2[no].push(max(ma,{-x.a,x.b}));
}
else{
tree[no].push(x);
tree2[no].push({-x.a,x.b});
}
return ;
}
tree[no].push(x);
tree2[no].push({-x.a,x.b});
*/
}
else{
int mid=(l+r)/2;
update2(no*2+1,l,mid,aa,bb,x,st);
update2(no*2+2,mid+1,r,aa,bb,x,st);
}
}
int query(int no,int l,int r,int i){
int cur=0;
while(tree[no].size()){
if(vis[(tree[no].top()).b]){
tree[no].pop();
}
else{
break;
}
}
while(tree2[no].size()){
if(vis[(tree2[no].top()).b]){
tree2[no].pop();
}
else{
break;
}
}
if(tree[no].size()){
//cout<<l<<","<<r<<","<<yy[i].a<<endl;
cur=max(cur,abs((tree[no].top()).a-yy[i].a));
cur=max(cur,abs(-(tree2[no].top()).a-yy[i].a));
}
if(l<r){
int mid=(l+r)/2;
if(i<=mid){
cur=max(cur,query(no*2+1,l,mid,i));
}
else{
cur=max(cur,query(no*2+2,mid+1,r,i));
}
}
return cur;
}
int query2(int no,int l,int r,int i){
int cur=0;
//cout<<l<<"<"<<r<<"<"<<yy[i].a<<"<"<<tree3[no][0]<<"<"<<tree3[no][1]<<endl;
cur=max(cur,yy[i].a-tree3[no][0]);
cur=max(cur,tree3[no][1]-yy[i].a);
if(l<r){
int mid=(l+r)/2;
if(i<=mid){
cur=max(cur,query2(no*2+1,l,mid,i));
}
else{
cur=max(cur,query2(no*2+2,mid+1,r,i));
}
}
return cur;
}
void add(int i,int aa,int bb,int st){
int mid=(aa+bb)/2;
if(kk==1){
if(st==1){
//cout<<aa<<","<<bb<<endl;
// xx[{i,{aa,mid}}]=ne;
pair<int,int> ind=solve(aa,mid);
update2(0,0,nn-1,ind.a,ind.b,aa,0);
//ne++;
//xx[{i,{mid+1,bb}}]=ne;
ind=solve(mid+1,bb);
update2(0,0,nn-1,ind.a,ind.b,bb,0);
//ne++;
}
return ;
}
if(st==1){
xx[{i,{aa,mid}}]=ne;
pair<int,int> ind=solve(aa,mid);
update(0,0,nn-1,ind.a,ind.b,{aa,ne},0);
ne++;
xx[{i,{mid+1,bb}}]=ne;
ind=solve(mid+1,bb);
update(0,0,nn-1,ind.a,ind.b,{bb,ne},1);
ne++;
}
else{
vis[xx[{i,{aa,mid}}]]=1;
vis[xx[{i,{mid+1,bb}}]]=1;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k>>q;
vector<pair<pair<int,int>,pair<int,int>>> cur;
vector<pair<int,int>> zz5;
for(int i=0;i<n;i++){
int x,aa,bb,tt;
cin>>x>>tt>>aa>>bb;
ss[x]++;
tt--;
if(aa!=1){
kk=0;
}
cur.pb({{aa,-1},{x,tt}});
cur.pb({{bb,1},{x,tt}});
// pre[tt].insert(x);
zz5.pb({tt,x});
}
for(int i=0;i<q;i++){
int x,aa;
cin>>x>>aa;
ss[x]++;
cur.pb({{aa,0},{x,i}});
ss3[x]++;
/*if(kk){
//pre[aa].insert(x);
}*/
}
if(kk){
for(auto j:zz5){
pre[j.a].insert(j.b);
}
for(int i=0;i<4*ss.size()+10;i++){
tree3[i][0]=1e8;
tree3[i][1]=0;
}
}
sort(cur.begin(),cur.end());
int ind5=-1;
ss[-2e8]++;
ss[2e8]++;
for(auto j:ss){
ind5++;
ss2[j.a]=ind5;
//yy.pb({j.a,ind5});
}
ind5=-1;
for(auto j:ss3){
ind5++;
ss4[j.a]=ind5;
yy.pb({j.a,ind5});
}
nn=yy.size();
//sort(cur.begin(),cur.end());
/*for(auto j:yy){
cout<<j.a<<",";
}
cout<<endl;*/
//cout<<kk<<endl;
for(int i=0;i<k;i++){
pre[i].insert(-2e8);
pre2[i][-2e8]++;
pre[i].insert(2e8);
pre2[i][2e8]++;
//if(kk==0){
/*if(kk==0){
add(i,-2e8,2e8,1);
}*/
// xx[{i,{-2e8,2e8}}]=;
// update(0,0,nn-1,0,nn-1);
}
for(int i=0;i<k;i++){
vector<int> xx;
for(auto j:pre[i]){
xx.pb(j);
}
/* for(auto j:xx){
cout<<j<<".";
}
cout<<endl;*/
for(int j=0;j+1<xx.size();j++){
add(i,xx[j],xx[j+1],1);
//cout<<i<<":"<<xx[j]<<":"<<xx[j+1]<<endl;
}
}
for(auto j:cur){
if(j.a.b==-1){
//add
/*if(kk){
continue;
}*/
//continue;
if(pre2[j.b.b].find(j.b.a)!=pre2[j.b.b].end()){
if(pre2[j.b.b][j.b.a]>0){
pre2[j.b.b][j.b.a]++;
continue;
}
}
//else{
pre2[j.b.b][j.b.a]++;
if(kk){
continue;
}
int re=*(pre[j.b.b].lower_bound(j.b.a));
auto jj=pre[j.b.b].lower_bound(j.b.a);
jj--;
int le=*jj;
pre[j.b.b].insert(j.b.a);
add(j.b.b,le,re,0);
add(j.b.b,le,j.b.a,1);
add(j.b.b,j.b.a,re,1);
//}
}
else if(j.a.b==1){
//remove
/*if(kk){
continue;
}*/
//continue;
pre2[j.b.b][j.b.a]--;
if(pre2[j.b.b][j.b.a]==0){
//cout<<11<<endl;
pre[j.b.b].erase(j.b.a);
int re=*(pre[j.b.b].lower_bound(j.b.a));
auto jj=pre[j.b.b].lower_bound(j.b.a);
jj--;
int le=*jj;
add(j.b.b,le,j.b.a,0);
add(j.b.b,j.b.a,re,0);
add(j.b.b,le,re,1);
}
}
else{
//cout<<j.b.a<<":"<<j.b.b<<endl;
if(kk){
int ans2=query2(0,0,nn-1,ss4[j.b.a]);
if(ans2>1e8){
ans2=-1;
}
ans[j.b.b]=ans2;
continue;
}
int ans2=query(0,0,nn-1,ss4[j.b.a]);
if(ans2>1e8){
ans2=-1;
}
ans[j.b.b]=ans2;
}
}
for(int i=0;i<q;i++){
cout<<ans[i]<<endl;
}
/*for(int i=0;i<cur.size();i++){
cur[i].b.a=ss2[cur[i].b.a];
}*/
return 0;
}
