#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10, inf=1e9;
long long stk[N*64];
int stk_size;
vector<pair<pair<int, int>, pair<int, int>>> vq[N];
int ans[N];
vector<pair<int, int>> vpos;
vector<int> vtime;
struct SegmentTree1{
int n;
pair<int, int> t[N*2];
void init(int _n){
n=_n;
for (int i=0; i<=n*2; ++i) t[i]={-inf, -inf};
}
void update(int pos, pair<int, int> val){
--pos;
pos+=n;
stk[++stk_size]=(((long long)pos)<<32)|(t[pos].first&((1ll<<32)-1));
stk[++stk_size]=(((long long)pos)<<32)|(t[pos].second&((1ll<<32)-1));
t[pos]=val;
for (; pos>1; pos>>=1){
stk[++stk_size]=(((long long)(pos>>1))<<32)|(t[pos>>1].first&((1ll<<32)-1));
stk[++stk_size]=(((long long)(pos>>1))<<32)|(t[pos>>1].second&((1ll<<32)-1));
t[pos>>1].first=max(t[pos].first, t[pos^1].first);
t[pos>>1].second=max(t[pos].second, t[pos^1].second);
}
}
int getl(int l, int r){
--l;
int res=-inf;
for (l+=n, r+=n; l<r; l>>=1, r>>=1){
if (l&1) res=max(res, t[l++].first);
if (r&1) res=max(res, t[--r].first);
}
return res;
}
int getr(int l, int r){
--l;
int res=-inf;
for (l+=n, r+=n; l<r; l>>=1, r>>=1){
if (l&1) res=max(res, t[l++].second);
if (r&1) res=max(res, t[--r].second);
}
return res;
}
} st1;
struct SegmentTree2{
int n;
vector<pair<int, pair<int, int>>> t[N*4];
void init(int _n){
n=_n;
}
void update(int k, int l, int r, int L, int R, pair<int, pair<int, int>> val){
if (r<L || R<l) return;
if (L<=l && r<=R){
t[k].push_back(val);
return;
}
int mid=(l+r)>>1;
update(k<<1, l, mid, L, R, val);
update(k<<1|1, mid+1, r, L, R, val);
}
void dfs(int k, int l, int r){
int size=stk_size;
for (auto &i:t[k]){
#ifdef sus
// cout << "update l " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
// cout << "update r " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
#endif
st1.update(i.first, {i.second.first+i.second.second, i.second.second-i.second.first});
}
if (l==r){
for (auto &i:vq[l]){
ans[i.second.first]=max(st1.getl(1, i.first.first)-i.second.second, st1.getr(i.first.second, st1.n)+i.second.second)/2;
}
}else{
int mid=(l+r)>>1;
dfs(k<<1, l, mid);
dfs(k<<1|1, mid+1, r);
}
while (stk_size!=size){
st1.t[stk[stk_size]>>32].second=(int)(stk[stk_size]&((1ll<<32)-1));
--stk_size;
st1.t[stk[stk_size]>>32].first=(int)(stk[stk_size]&((1ll<<32)-1));
--stk_size;
}
}
} st2;
int n, q, k;
vector<pair<int, int>> v[N];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> q;
vtime.push_back(-inf*2); vpos.emplace_back(-inf*2, -1);
vector<pair<int, pair<int, int>>> check;
{
vector<array<int, 4>> mp, mp2;
for (int i=1; i<=n; ++i){
int x, t, l, r;
cin >> x >> t >> l >> r; x*=2;
mp.push_back({x, t, l, r});
}
sort(mp.begin(), mp.end());
for (int i=0; i<(int)mp.size(); ){
int j=i;
while (j+1<(int)mp.size() && mp[i][0]==mp[j+1][0] && mp[i][1]==mp[j+1][1]) ++j;
for (; i<=j; ++i){
if (mp2.size() && mp2.back()[0]==mp[i][0] && mp2.back()[1]==mp[i][1] && mp2.back()[3]+1>=mp[i][2]){
mp2.back()[3]=max(mp2.back()[3], mp[i][3]);
}else mp2.push_back(mp[i]);
}
}
for (auto &i:mp2){
int x=i[0], t=i[1], l=i[2], r=i[3];
v[t].emplace_back(l, x);
v[t].emplace_back(r+1, -x);
check.push_back({l, {1, t}});
check.push_back({r+1, {-1, t}});
}
}
vector<vector<int>> events;
for (int i=1; i<=k; ++i){
set<int> st;
unordered_map<int, int> mp;
sort(v[i].begin(), v[i].end());
for (auto &j:v[i]){
int pos=abs(j.second), t=j.first;
auto it=st.lower_bound(pos);
if (j.second>0){
if (st.size()){
int x=0, y=0;
if (it==st.begin()) x=-*it, y=*it*2;
else if (it==st.end()) x=inf+*prev(it), y=inf;
else x=(*it+*prev(it))>>1, y=(*it-*prev(it))>>1;
events.push_back({mp[x], t-1, x, y});
mp.erase(x);
}
{
int x=0;
if (it==st.begin()) x=-pos;
else x=(pos+*prev(it))>>1;
mp[x]=t;
}
{
int x=0;
if (it==st.end()) x=inf+pos;
else x=(*it+pos)>>1;
mp[x]=t;
}
st.emplace_hint(it, pos);
}else{
{
int x=0, y=0;
if (it==st.begin()) x=-pos, y=pos*2;
else x=(pos+*prev(it))>>1, y=(pos-*prev(it))>>1;
events.push_back({mp[x], t-1, x, y});
mp.erase(x);
}
{
int x=0, y=0;
if (next(it)==st.end()) x=inf+pos, y=inf;
else x=(*next(it)+pos)>>1, y=(*next(it)-pos)>>1;
events.push_back({mp[x], t-1, x, y});
mp.erase(x);
}
if ((int)st.size()>1){
int x=0;
if (it==st.begin()) x=-*next(it);
else if (next(it)==st.end()) x=inf+*prev(it);
else x=(*next(it)+*prev(it))>>1;
mp[x]=t;
}
st.erase(it);
}
}
}
for (int i=0; i<(int)events.size(); ++i){
vpos.emplace_back(events[i][2], i);
}
sort(vpos.begin(), vpos.end());
vector<pair<int, int>> query(q);
for (auto &i:query) cin >> i.first >> i.second, vtime.push_back(i.second), i.first*=2;
sort(vtime.begin(), vtime.end()); vtime.resize(unique(vtime.begin(), vtime.end())-vtime.begin());
for (int i=1; i<=q; ++i){
int pl=lower_bound(vpos.begin(), vpos.end(), make_pair(query[i-1].first, -inf))-vpos.begin();
int pr=lower_bound(vpos.begin(), vpos.end(), make_pair(query[i-1].first, inf))-vpos.begin()-1;
vq[lower_bound(vtime.begin(), vtime.end(), query[i-1].second)-vtime.begin()].push_back({{pr, pl}, {i, query[i-1].first}});
check.push_back({query[i-1].second, {2, i}});
}
st1.init((int)vpos.size()-1);
st2.init((int)vtime.size()-1);
for (int i=0; i<(int)events.size(); ++i){
events[i][0]=lower_bound(vtime.begin(), vtime.end(), events[i][0])-vtime.begin();
events[i][1]=upper_bound(vtime.begin(), vtime.end(), events[i][1])-vtime.begin()-1;
if (events[i][0]<=events[i][1]) st2.update(1, 1, st2.n, events[i][0], events[i][1], {lower_bound(vpos.begin(), vpos.end(), make_pair(events[i][2], i))-vpos.begin(), {events[i][2], events[i][3]}});
}
st2.dfs(1, 1, st2.n);
sort(check.begin(), check.end());
vector<int> cnt(k+1); int cnt0=k;
for (auto &i:check){
if (abs(i.second.first)==1){
cnt0-=!cnt[i.second.second];
cnt[i.second.second]+=i.second.first;
cnt0+=!cnt[i.second.second];
}else{
if (cnt0) ans[i.second.second]=-1;
}
}
for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
return 0;
}
