#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
ll N,K,Q;
const ll Nm = (1<<20); const ll E = 20;
const ll INF = 5e8;
ll ans[Nm];
multiset<ll> st1[2*Nm]; //store C in x+C
multiset<ll> st2[2*Nm]; //store C in -x+C
map<ll,ll> cvrt;
ll qry(ll x) {
auto A0 = --cvrt.upper_bound(x);
ll y = (*A0).second;
ll fval = -INF;
for (ll e=0;e<E;e++) {
fval = max(fval,x+*(prev(st1[(y>>e)+(1<<(E-e))].end())));
fval = max(fval,-x+*(prev(st2[(y>>e)+(1<<(E-e))].end())));
}
return fval;
}
inline ll v2(ll x) {
return __builtin_ctz(x);
}
void ins1(ll a, ll b, ll v) {
if (a>b) {
return;
}
ll va = v2(a); ll vb = v2(b+1);
if (va<vb) {
ll p = (a>>va)+(1<<(E-va));
st1[p].insert(v);
ins1(a+(1<<va),b,v);
} else {
ll p = (b>>vb)+(1<<(E-vb));
st1[p].insert(v);
ins1(a,b-(1<<vb),v);
}
}
void ins2(ll a, ll b, ll v) {
if (a>b) {
return;
}
ll va = v2(a); ll vb = v2(b+1);
if (va<vb) {
ll p = (a>>va)+(1<<(E-va));
st2[p].insert(v);
ins2(a+(1<<va),b,v);
} else {
ll p = (b>>vb)+(1<<(E-vb));
st2[p].insert(v);
ins2(a,b-(1<<vb),v);
}
}
void del1(ll a, ll b, ll v) {
if (a>b) {
return;
}
ll va = v2(a); ll vb = v2(b+1);
if (va<vb) {
ll p = (a>>va)+(1<<(E-va));
st1[p].erase(st1[p].find(v));
del1(a+(1<<va),b,v);
} else {
ll p = (b>>vb)+(1<<(E-vb));
st1[p].erase(st1[p].find(v));
del1(a,b-(1<<vb),v);
}
}
void del2(ll a, ll b, ll v) {
if (a>b) {
return;
}
ll va = v2(a); ll vb = v2(b+1);
if (va<vb) {
ll p = (a>>va)+(1<<(E-va));
st2[p].erase(st2[p].find(v));
del2(a+(1<<va),b,v);
} else {
ll p = (b>>vb)+(1<<(E-vb));
st2[p].erase(st2[p].find(v));
del2(a,b-(1<<vb),v);
}
}
void ins(ll a, ll b) {
if (a==-INF) {
ins2(cvrt[a],cvrt[b],b);
return;
}
if (b==INF) {
ins1(cvrt[a],cvrt[b],-a);
return;
}
ll ya = cvrt[a];
ll ym = cvrt[(a+b+1)/2];
ll yb = cvrt[b];
ins1(ya,ym-1,-a);
ins2(ym,yb-1,b);
}
void del(ll a, ll b) {
if (a==-INF) {
del2(cvrt[a],cvrt[b],b);
return;
}
if (b==INF) {
del1(cvrt[a],cvrt[b],-a);
return;
}
ll ya = cvrt[a];
ll ym = cvrt[(a+b+1)/2];
ll yb = cvrt[b];
del1(ya,ym-1,-a);
del2(ym,yb-1,b);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> K >> Q;
for (ll i=0;i<(2*Nm);i++) {
st1[i].insert(-INF);
st2[i].insert(-INF);
}
map<ll,ll> m0[K];
vector<array<ll,4>> upd;
set<ll> sx;
for (ll i=0;i<N;i++) {
ll x,t,a,b; cin >> x >> t >> a >> b;
t--;
upd.push_back({a,1,x,t});
upd.push_back({b+1,2,x,t});
}
for (ll q=0;q<Q;q++) {
ll l,y; cin >> l >> y;
upd.push_back({y,3,l,q});
}
for (ll k=0;k<K;k++) {
m0[k][-INF]=1;
m0[k][INF]=1;
}
sort(upd.begin(),upd.end());
sx.insert(-INF);
sx.insert(INF);
for (auto A0: upd) {
//cout << "A0: "<<A0[0]<<", "<<A0[1]<<", "<<A0[2]<<", "<<A0[3]<<"\n";
//continue;
if (A0[1]==1) {
ll t = A0[3];
ll x = A0[2];
sx.insert(x);
if (m0[t].find(x)==m0[t].end()) {
m0[t][x]=1;
auto A1 = m0[t].find(x);
ll P0 = (*prev(A1)).first;
ll N0 = (*next(A1)).first;
if (P0 != -INF) {
sx.insert((x+P0+1)/2);
}
if (N0 != INF) {
sx.insert((x+N0+1)/2);
}
} else {
m0[t][x]++;
}
} else if (A0[1]==2) {
ll t = A0[3];
ll x = A0[2];
assert(m0[t].find(x)!=m0[t].end());
if (m0[t][x]==1) {
auto A1 = m0[t].find(x);
ll P0 = (*prev(A1)).first;
ll N0 = (*next(A1)).first;
if (P0 != -INF && N0 != INF) {
sx.insert((P0+N0+1)/2);
}
m0[t].erase(m0[t].find(x));
} else {
m0[t][x]--;
}
}
}
assert(sx.size()<=Nm);
ll icv = 0;
for (ll x: sx) {
//cout << "x in sx="<<x<<"\n";
cvrt[x]=(icv++);
}
for (ll k=0;k<K;k++) {
m0[k].clear();
m0[k][-INF]=1;
m0[k][INF]=1;
ins(-INF,INF);
}
ll NACT = 0;
//exit(0);
for (auto A0: upd) {
//cout << "A0: "<<A0[0]<<", "<<A0[1]<<", "<<A0[2]<<", "<<A0[3]<<"\n";
if (A0[1]==1) {
ll t = A0[3];
ll x = A0[2];
if (m0[t].size()==2) {
NACT++;
}
if (m0[t].find(x)==m0[t].end()) {
m0[t][x]=1;
auto A1 = m0[t].find(x);
del((*prev(A1)).first,(*next(A1)).first);
ins((*prev(A1)).first,x);
ins(x,(*next(A1)).first);
} else {
m0[t][x]++;
}
} else if (A0[1]==2) {
ll t = A0[3];
ll x = A0[2];
if (m0[t][x]==1) {
auto A1 = m0[t].find(x);
ins((*prev(A1)).first,(*next(A1)).first);
del((*prev(A1)).first,x);
del(x,(*next(A1)).first);
m0[t].erase(m0[t].find(x));
if (m0[t].size()==2) {
NACT--;
}
} else {
m0[t][x]--;
}
} else {
if (NACT<K) {
ans[A0[3]]=-1;
} else {
ans[A0[3]]=qry(A0[2]);
}
}
}
for (ll i=0;i<Q;i++) {
cout << ans[i] << "\n";
}
}
