// In the name of God
// We are everywhere while we are nowhere(Haj NEZAM...)
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define lc 2 * v
#define nt(v) v ^ 1
#define rc 2 * v + 1
#define PB push_back
#define MP make_pair
#define ll long long
// #define int long long
#define ld long double
#define mid (s + e) / 2
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define _all(e) e.begin() , e.end()
#define pll pair <long long , long long>
#define piii pair <int , pair <int , int> >
#define FAST ios::sync_with_stdio(0);cin.tie(0)
#define UNI(e) e.resize(unique(_all(e)) - e.begin())
#define kill(e) cout << e << '\n'
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,avx")
#pragma GCC optimize("O3,unroll-loops")
const int maxn = 6e5 + 5 , N = 400 + 5 , SQ = 55 , base = 879169 , mod = 1e9 + 7 , INF = 1e9 + 5 , lg = 11;
const ld eps = 1e-6;
struct node {
int mnL = INF , mxR = -INF;
};
node seg[4 * maxn];
int x[maxn] , t[maxn] , a[maxn] , b[maxn] , ql[maxn] , qx[maxn];
int n , k , q , SZ , cnt_zero , res[maxn] , L[maxn] , R[maxn];
vector <piii> vec , comp1;
set <pii> active[maxn];
vector <int> comp2;
void compress() {
sort(_all(comp1)) , sort(_all(comp2));
UNI(comp2);
for (int i = 0; i < n; ++i) {
a[i] = lower_bound(_all(comp2) , a[i]) - comp2.begin();
b[i] = lower_bound(_all(comp2) , b[i]) - comp2.begin();
vec.PB({a[i] , {0 , i}}) , vec.PB({b[i] , {2 , i}});
}
for (int i = 0; i < q; ++i) {
ql[i] = lower_bound(_all(comp2) , ql[i]) - comp2.begin();
vec.PB({ql[i] , {1 , i}});
}
for (int i = 0; i < n + q; ++i) {
if(!comp1[i].S.F) x[comp1[i].S.S] = i;
else qx[comp1[i].S.S] = i;
}
sort(_all(vec));
}
void modify_L(int p , int r , int v = 1 , int s = 0 , int e = SZ) {
if(e - s == 1) {
L[s] = r;
seg[v].mnL = (r != INF && r != -INF ? comp1[r].F + comp1[s].F : r);
return ;
}
if(p < mid) modify_L(p , r , lc , s , mid);
else modify_L(p , r , rc , mid , e);
seg[v].mnL = min(seg[lc].mnL , seg[rc].mnL);
}
void modify_R(int p , int r , int v = 1 , int s = 0 , int e = SZ) {
if(e - s == 1) {
R[s] = r;
seg[v].mxR = (r != INF && r != -INF ? comp1[r].F + comp1[s].F : r);
return ;
}
if(p < mid) modify_R(p , r , lc , s , mid);
else modify_R(p , r , rc , mid , e);
seg[v].mxR = max(seg[lc].mxR , seg[rc].mxR);
}
int get_L(int l , int r , int p , int v = 1 , int s = 0 , int e = SZ) {
if(l >= e || s >= r || seg[v].mnL > p) return -1;
if(e - s == 1) return s;
int res = get_L(l , r , p , rc , mid , e);
return (res != -1 ? res : get_L(l , r , p , lc , s , mid));
}
int get_R(int l , int r , int p , int v = 1 , int s = 0 , int e = SZ) {
if(l >= e || s >= r || seg[v].mxR < p) return -1;
if(e - s == 1) return s;
int res = get_R(l , r , p , lc , s , mid);
return (res != -1 ? res : get_R(l , r , p , rc , mid , e));
}
void add_store(int st) {
// if(a[st] <= ql[0] && ql[0] <= b[st])
// cout << "ADD STORE " << st << ' ' << t[st] << ' ' << x[st] << endl;
if(!_sz(active[t[st]])) cnt_zero--;
set <pii> ::iterator it = active[t[st]].lower_bound({x[st] , -1});
R[x[st]] = (it != active[t[st]].end() ? it -> F : INF);
L[x[st]] = (it != active[t[st]].begin() ? (--it) -> F : -INF);
active[t[st]].insert({x[st] , st});
modify_L(x[st] , L[x[st]]) , modify_R(x[st] , R[x[st]]);
if(R[x[st]] != INF) modify_L(R[x[st]] , x[st]);
if(L[x[st]] != -INF) modify_R(L[x[st]] , x[st]);
}
void rem_store(int st) {
// cout << "REM STORE " << st << ' ' << x[st] << endl;
if(R[x[st]] != INF) modify_L(R[x[st]] , L[x[st]]);
if(L[x[st]] != -INF) modify_R(L[x[st]] , R[x[st]]);
modify_L(x[st] , INF) , modify_R(x[st] , -INF);
active[t[st]].erase({x[st] , st});
if(!_sz(active[t[st]])) cnt_zero++;
}
int32_t main() {
FAST;
cin >> n >> k >> q;
for (int i = 0; i < n; ++i) {
cin >> x[i] >> t[i] >> a[i] >> b[i];
comp1.PB({x[i] , {0 , i}}) , comp2.PB(a[i]) , comp2.PB(b[i]);
}
for (int i = 0; i < q; ++i) {
cin >> qx[i] >> ql[i];
comp1.PB({qx[i] , {1 , i}}) , comp2.PB(ql[i]);
}
compress();
cnt_zero = k;
SZ = _sz(comp1);
fill(L , L + maxn , INF);
fill(R , R + maxn , -INF);
// for (int i = 0; i < n; ++i) {
// cout << x[i] << ' ' << t[i] << ' ' << a[i] << ' ' << b[i] << endl;
// }
// cout << endl;
// for (auto cur : comp1) {
// cout << cur.F << ' ' << cur.S.F << ' ' << cur.S.S << endl;
// }
// cout << endl;
for (auto f : vec) {
if(f.S.F == 0) {
add_store(f.S.S);
}
else if(f.S.F == 1) {
int qu = f.S.S;
if(cnt_zero) {
res[qu] = -1; continue;
}
// cout << qu << ' ' << qx[qu] << ' ' << ql[qu] << endl;
int intial = comp1[qx[qu]].F;
int pos1 = get_R(0 , qx[qu] + 1 , intial * 2);
int pos2 = get_L(qx[qu] , SZ , intial * 2);
int val1 = (pos1 == -1 ? INF : comp1[pos1].F);
int val2 = (pos2 == -1 ? -INF : comp1[pos2].F);
// cout << pos1 << ' ' << pos2 << endl;
res[qu] = max(0 , max(intial - val1 , val2 - intial));
}
else {
rem_store(f.S.S);
}
}
for (int i = 0; i < q; ++i) {
cout << res[i] << '\n';
}
}
