#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
inline int rd(){
int x=0;
char ch=getchar_unlocked();
while(ch<'0'||ch>'9')ch=getchar_unlocked();
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar_unlocked();
}
return x;
}
struct upd{
int s,e,p,x;
};
struct qry{
int l,y,i;
};
#define maxn 300005
int n,k,m,q,x[maxn],t[maxn],a[maxn],b[maxn],l[maxn],y[maxn],ltime[maxn],rtime[maxn],ans[maxn];
bool impos[2*maxn];
vi add[2*maxn],rem[2*maxn];
set<ii> s[2*maxn];
vector<upd> pupd,nupd;
void add_upd(ii ss,ii ee,int t){
//pf("add_upd: %d %d %d %d %d\n",ss.fi,ss.se,ee.fi,ee.se,t);
if(ss.se!=0&&rtime[ss.se]<t){
pupd.pb({rtime[ss.se],t-1,(ss.fi+ee.fi)/2,x[ss.se]});
rtime[ss.se]=t;
}
if(ee.se!=0&<ime[ee.se]<t){
nupd.pb({ltime[ee.se],t-1,(ss.fi+ee.fi+1)/2,x[ee.se]});
ltime[ee.se]=t;
}
}
void dnc(int s,int e,vector<qry> &qrys,vector<upd> &pupd,vector<upd> &nupd){
if(s>e||qrys.empty()||(pupd.empty()&&nupd.empty()))return;
int m=(s+e)/2;
vector<qry> lqrys,rqrys;
vector<upd> lpupd,lnupd,rpupd,rnupd;
#ifdef DEBUG
pf("dnc: %d %d\n",s,e);
for(qry &q:qrys)pf("(%d %d %d) ",q.l,q.y,q.i);pf("\n");
pf("pupd: ");for(upd &u:pupd)pf("(%d %d %d %d) ",u.s,u.e,u.p,u.x);pf("\n");
pf("nupd: ");for(upd &u:nupd)pf("(%d %d %d %d) ",u.s,u.e,u.p,u.x);pf("\n");
pf("\n");
#endif //DEBUG
int ptr=0,cur=0;
for(qry &q:qrys){
while(ptr!=sz(nupd)&&nupd[ptr].p<=q.l){
if(nupd[ptr].s<=s&&e<=nupd[ptr].e)cur=max(cur,nupd[ptr].x);
else{
if(nupd[ptr].s<=m)lnupd.pb(nupd[ptr]);
if(m+1<=nupd[ptr].e)rnupd.pb(nupd[ptr]);
}
++ptr;
}
mxto(ans[q.i],cur-q.l);
if(q.y<=m)lqrys.pb(q);
else rqrys.pb(q);
}
ptr=0,cur=2e8;
reverse(all(qrys));
for(qry &q:qrys){
while(ptr!=sz(pupd)&&pupd[ptr].p>=q.l){
if(pupd[ptr].s<=s&&e<=pupd[ptr].e)cur=min(cur,pupd[ptr].x);
else{
if(pupd[ptr].s<=m)lpupd.pb(pupd[ptr]);
if(m+1<=pupd[ptr].e)rpupd.pb(pupd[ptr]);
}
++ptr;
}
mxto(ans[q.i],q.l-cur);
}
dnc(s,m,lqrys,lpupd,lnupd);
dnc(m+1,e,rqrys,rpupd,rnupd);
}
int main(){
//read input and discretise
n=rd();k=rd();q=rd();
vector<int> d;
for(int i=1;i<=n;++i){
x[i]=rd();t[i]=rd();a[i]=rd();b[i]=rd();
d.pb(a[i]);d.pb(b[i]+1);
}
d.pb(0);
disc(d);m=sz(d);
for(int i=1;i<=n;++i){
a[i]=upper_bound(all(d),a[i])-d.begin()-1;
b[i]=upper_bound(all(d),b[i])-d.begin()-1;
add[a[i]].pb(i);
rem[b[i]+1].pb(i);
}
vector<qry> qrys;
for(int i=0;i<q;++i){
l[i]=rd();y[i]=rd();
y[i]=upper_bound(all(d),y[i])-d.begin()-1;
qrys.pb({l[i],y[i],i});
}
sort(all(qrys),[](qry &a,qry &b){return a.l<b.l;});
int zero=k;
//preprocess lines
for(int i=0;i<m;++i){
for(int j:rem[i]){
//pf("rem %d\n",j);
ii ss={-2e8,0},ee={2e8,0},mm={x[j],j};
auto it=s[t[j]].upper_bound({x[j],j});
if(it!=s[t[j]].end())ee=*it;
it=s[t[j]].lower_bound({x[j],j});
if(it!=s[t[j]].begin())ss=*--it;
add_upd(ss,mm,i);add_upd(mm,ee,i);
s[t[j]].erase(s[t[j]].find({x[j],j}));
if(s[t[j]].empty())++zero;
}
for(int j:add[i]){
//pf("add %d\n",j);
ii ss={-2e8,0},ee={2e8,0};
auto it=s[t[j]].upper_bound({x[j],j});
if(it!=s[t[j]].end())ee=*it;
if(it!=s[t[j]].begin())ss=*--it;
add_upd(ss,ee,i);
rtime[j]=ltime[j]=i;
if(s[t[j]].empty())--zero;
s[t[j]].insert({x[j],j});
}
if(zero>0)impos[i]=true;
}
sort(all(pupd),[](upd &a,upd &b){return a.p>b.p;});
sort(all(nupd),[](upd &a,upd &b){return a.p<b.p;});
dnc(0,m-1,qrys,pupd,nupd);
for(int i=0;i<q;++i){
if(impos[y[i]])pf("-1\n");
else pf("%d\n",ans[i]);
}
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
3 1 3
1 1 1 5
3 1 2 3
3 1 3 4
1 1
3 3
2 5
*/
