#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second
#define db 0
#define EPS (1e-7) //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, q, k;
tuple <ll, ll, ll, ll> A[MAXN]; // l, type, a, b
spi Q[MAXN];
ll ans[MAXN];
multiset <ll> ms[MAXN];
priority_queue <pi, vector<pi>,greater<pi>> pq;
void st1_2() {
sort(Q,Q+q); sort(A,A+n, [] (tuple<ll,ll,ll,ll>x,tuple<ll,ll,ll,ll>y) { return get<2>(x) < get<2>(y); });
ll co = 0;
FOR(i,0,q) {
ll t = Q[i].f, l = Q[i].s.f, ind = Q[i].s.s;
while(co < n && t >= get<2>(A[co])) {
ms[get<1>(A[co])].ins(get<0>(A[co]));
pq.ph(pi(get<3>(A[co]),co));++co;
}
while(pq.size() && pq.top().f < t) ms[get<1>(A[pq.top().s])].erase(ms[get<1>(A[pq.top().s])].find(get<0>(A[pq.top().s]))), pq.pop();
ll anss = -1;
FOR(i,1,k+1) {
if(ms[i].empty()) { anss=INF; continue; }
auto itr = ms[i].lower_bound(l);
ll best = INF;
if(itr != ms[i].end()) best=min(best, *itr-l);
if(itr == ms[i].begin());
else {
--itr;
best=min(best, l-*itr);
}
// assert(best != LLINF);
anss=max(anss,best);
}
if(anss==INF) anss=-1;
ans[ind]=anss;
}
FOR(i,0,q) cout << ans[i] << '\n';
}
map <ll, ll> mp; // x, y
multiset<ll>types[MAXN];
ll STORECO[MAXN];
void check_removal_neg(map<ll,ll>::iterator itr) {
while(itr != mp.end()) {
auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
else { break; }
assert(val == itr->f);
}
}
void add_neg(ll xx, ll val) {
mp[xx] = max(mp[xx],val);
auto itr = mp.lower_bound(xx);
while(itr != mp.end()) {
auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
else { break; }
assert(val == itr->f);
}
if(itr!=mp.begin())check_removal_neg(prev(itr));
return;
}
bool remove_neg(ll &co, ll time) {
while(co < n && get<3>(A[co]) < time) {
ll l,type,a,b; tie(l,type,a,b)=A[co]; ++co;
STORECO[type] --;
if(STORECO[type] <= 0) return 0;
auto itr = types[type].lower_bound(l);//assert(itr!=types[type].end());
if(itr == types[type].begin()) {
assert(next(itr)!=types[type].end());
add_neg(1, *next(itr)-1);
} else if(next(itr) != types[type].end()) {
add_neg(((*next(itr) + *prev(itr) + 1)/2), llabs( ((*next(itr) + *prev(itr) + 1)/2) - *next(itr) ));
}
types[type].erase(itr);
}
return 1;
}
void check_removal_pos(map<ll,ll>::iterator itr) {
while(itr!=mp.begin()) {
auto itr2 = prev(itr); ll val = itr->f;
if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
else break;
assert(val==itr->f);
}
return;
}
void add_pos(ll xx, ll val) {
mp[xx]=max(mp[xx],val);
auto itr = mp.lower_bound(xx);
while(itr!=mp.begin()) {
auto itr2 = prev(itr); ll val = itr->f;
if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
else break;
assert(val==itr->f);
}
if(next(itr) != mp.end()) check_removal_pos(next(itr));
return;
}
bool remove_pos(ll &co, ll time) {
while(co < n && get<3>(A[co]) < time) {
ll l,type,a,b; tie(l,type,a,b)=A[co]; ++co;
STORECO[type] --;
if(STORECO[type]<=0) return 0;
auto itr = types[type].lower_bound(l); //assert(itr!=types[type].end());
if(itr == prev(types[type].end())) {
add_pos(INF, INF-*prev(itr));
} else if(itr != types[type].begin()) {
add_pos(((*next(itr) + *prev(itr))/2), llabs( ((*next(itr) + *prev(itr))/2) - *prev(itr) ));
}
types[type].erase(itr);
}
return 1;
}
void st3_4() {
sort(Q,Q+q);
sort(A,A+n,[](tuple<ll,ll,ll,ll>x,tuple<ll,ll,ll,ll>y) { return get<3>(x) < get<3>(y); });
FOR(i,0,n) {
types[get<1>(A[i])].ins(get<0>(A[i])); STORECO[get<1>(A[i])]++; // assert(!duplicate[get<0>(A[i])]); duplicate[get<0>(A[i])] = 1;
}
FOR(K,1,k+1) {
/*sort(all(types[K])); types[K].resize(unique(all(types[K]))-types[K].begin());*/ if(types[K].empty()) { FOR(i,0,q) cout << "-1\n"; exit(0); }
for(auto i = next(types[K].begin()); i != types[K].end(); i++) {
mp[(*i+*prev(i)+1)/2] = max(mp[(*i+*prev(i)+1)/2],llabs(*i-(*i+*prev(i)+1)/2));
}
mp[1]=max(mp[1],*types[K].begin()-1);
}
for(auto itr = mp.begin(); itr != mp.end(); itr ++) {
while(itr != mp.end()) {
auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
else { break; }
assert(val == itr->f);
}
}
ll co = 0; bool stillcan = 1;
FOR(i,0,q) { if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
ll l = Q[i].s.f, t = Q[i].f; stillcan &= remove_neg(co,t); if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
auto itr = mp.upper_bound(l);
assert(itr != mp.begin()); // even if size is one, itr will be ms.end()
--itr;
ans[Q[i].s.s] = itr->s - (l-itr->f);
}
mp.clear(); mmst(STORECO,0); FOR(i,1,k+1) types[i].clear(); FOR(i,0,n) { types[get<1>(A[i])].ins(get<0>(A[i])); STORECO[get<1>(A[i])]++; }
FOR(K,1,k+1) {
for(auto i = types[K].begin(); i != prev(types[K].end()); i ++) {
mp[(*i+*next(i))/2] = max(mp[(*i+*next(i))/2],llabs((*i+*next(i))/2-*i));
}
mp[INF]=max(mp[INF],INF-(*--types[K].end()));
}
for(auto itr = mp.begin(); itr != mp.end(); itr ++) {
while(itr!=mp.begin()) {
auto itr2 = prev(itr); ll val = itr->f;
if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
else break;
assert(val==itr->f);
}
}
co = 0;stillcan = 1;
FOR(i,0,q) { if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
ll l = Q[i].s.f, t = Q[i].f; stillcan &= remove_pos(co,t); if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
auto itr = mp.lower_bound(l);
// assert(itr != mp.end());
ans[Q[i].s.s] = max(ans[Q[i].s.s], itr->s - (itr->f-l));
}
FOR(i,0,q)if(ans[i]==-INF){ans[i]=-1;}
FOR(i,0,q) cout << ans[i] << '\n';
}
int main()
{ // freopen("int","r",stdin);
FAST
cin>>n>>k>>q;
FOR(i,0,n) {
ll a,b,c,d;cin>>a>>b>>c>>d;
A[i]=make_tuple(a,b,c,d);
}
FOR(i,0,q) {
ll l,t;
cin>>l>>t;
Q[i]=spi(t,pi(l,i));
}
if(k<=400&&n<=6*1e4&&q<=6*1e4) { st1_2(); return 0; }
else {
st3_4(); return 0;
}
}
/*
*
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
*
*
*
* to fit st3_4 sol *
4 2 4
3 1 1 10
9 2 1 4
7 2 1 7
4 1 1 10
5 3
5 6
5 9
1 10
*
*Ans:
* 2
* 2
* -1
* -1
*/
