#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e8;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct store
{
int x,l,r;
};
struct event
{
int time,poz,beg,type;
bool operator<(const event& other) const
{
if(time != other.time) return time<other.time;
return type>other.type;
}
};
struct query
{
int time,poz,ind;
bool operator<(const query& other) const
{
return time<other.time;
}
};
const int tree_siz = 1024*1024-1;
struct segtree
{
int max_[tree_siz+1];
multiset<int> begs[tree_siz/2+1];
segtree()
{
rep(i,tree_siz+1) max_[i] = -1e9;
}
int get_max(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return -1e9;
if(p1 >= s1 && p2 <= s2) return max_[akt];
return max(get_max(akt*2,p1,(p1+p2)/2,s1,s2),get_max(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}
void upd(int v)
{
max_[v] = max(max_[v*2],max_[v*2+1]);
if(v != 1) upd(v/2);
}
void change(int p, int b, int type)
{
if(type == 1) begs[p].insert(b);
else begs[p].erase(begs[p].find(b));
max_[tree_siz/2+1+p] = (siz(begs[p]) != 0 ? *(--begs[p].end()) : -1e9);
upd((tree_siz/2+1+p)/2);
}
};
int query_ans[300001];
int k_cnt[300001];
vector<store> stores[300001];
segtree suf_tree;
segtree pref_tree;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n,q,k;
cin >> n >> k >> q;
rep(i,n)
{
int x,t,l,r;
cin >> x >> t >> l >> r;
stores[t].pb({x,l,r});
}
vector<event> suf_events;
vector<event> pref_events;
vector<pii> cnt_events;
rep2(t2,1,k)
{
set<int> cur;
map<int,int> cnt;
vector<pii> events;
forall(it,stores[t2])
{
cnt_events.pb({it.l,t2});
cnt_events.pb({it.r+1,-t2});
events.pb({it.l,it.x});
events.pb({it.r+1,-it.x});
}
sort(all(events));
forall(it,events)
{
int x = it.ss;
int t = it.ff;
int p = -1;
if(x <= 0)
{
x *= -1;
cnt[x]--;
if(cnt[x] != 0) continue;
cur.erase(x);
}
else
{
cnt[x]++;
if(cnt[x] != 1) continue;
p = 1;
}
auto nxt = cur.lower_bound(x);
int nx = -1;
int pv = -1;
if(nxt != cur.end())
{
pref_events.pb({t,(x+*nxt)/2,-x,p});
suf_events.pb({t,(x+*nxt+1)/2,-(INF-*nxt),p});
nx = *nxt;
}
else
{
pref_events.pb({t,INF,-x,p});
}
if(nxt != cur.begin())
{
nxt--;
suf_events.pb({t,(x+*nxt+1)/2,-(INF-x),p});
pref_events.pb({t,(x+*nxt)/2,-*nxt,p});
pv = *nxt;
}
else
{
suf_events.pb({t,0,-(INF-x),p});
}
if(pv != -1)
{
if(nx != -1) pref_events.pb({t,(pv+nx)/2,-pv,-p});
else pref_events.pb({t,INF,-pv,-p});
}
if(nx != -1)
{
if(pv != -1) suf_events.pb({t,(pv+nx+1)/2,-(INF-nx),-p});
else suf_events.pb({t,0,-(INF-nx),-p});
}
if(p == 1) cur.insert(x);
}
}
vector<query> queries;
rep(qq,q)
{
int p,t;
cin >> p >> t;
queries.pb({t,p,qq});
}
sort(all(queries));
sort(all(pref_events));
sort(all(suf_events));
sort(all(cnt_events));
int cur = 1;
map<int,int> mp;
map<int,int> rel_ind;
forall(it,queries) mp[it.poz] = 1;
forall(it,mp)
{
rel_ind[cur] = it.ff;
mp[it.ff] = cur++;
}
forall(it,queries) it.poz = mp[it.poz];
forall(it,pref_events)
{
auto pv = mp.upper_bound(it.poz);
if(pv == mp.begin()) it.poz = 0;
else it.poz = (*--pv).ss;
}
forall(it,suf_events)
{
auto nx = mp.lower_bound(it.poz);
if(nx == mp.end()) it.poz = cur;
else it.poz = (*nx).ss;
}
int cur_pref = 0, cur_suf = 0, cur_cnt = 0;
int zero_cnt = k;
forall(it,queries)
{
while(cur_pref != siz(pref_events) && pref_events[cur_pref].time <= it.time)
{
pref_tree.change(pref_events[cur_pref].poz,pref_events[cur_pref].beg,pref_events[cur_pref].type);
cur_pref++;
}
while(cur_suf != siz(suf_events) && suf_events[cur_suf].time <= it.time)
{
suf_tree.change(suf_events[cur_suf].poz,suf_events[cur_suf].beg,suf_events[cur_suf].type);
cur_suf++;
}
while(cur_cnt != siz(cnt_events) && cnt_events[cur_cnt].ff <= it.time)
{
if(cnt_events[cur_cnt].ss <= 0)
{
k_cnt[-cnt_events[cur_cnt].ss]--;
if(k_cnt[-cnt_events[cur_cnt].ss] == 0) zero_cnt++;
}
else
{
k_cnt[cnt_events[cur_cnt].ss]++;
if(k_cnt[cnt_events[cur_cnt].ss] == 1) zero_cnt--;
}
cur_cnt++;
}
if(zero_cnt != 0) query_ans[it.ind] = -1;
else query_ans[it.ind] = max(pref_tree.get_max(1,0,tree_siz/2,it.poz,cur)+rel_ind[it.poz],suf_tree.get_max(1,0,tree_siz/2,0,it.poz)+INF-rel_ind[it.poz]);
}
rep(qq,q) cout << query_ans[qq] << "\n";
}
