#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5;
const int MAXV = 1e8;
int n, k, q;
class event {
public:
int time;
bool type; // 0 update, 1 query
bool start_or_end; // 0 start, 1 end. Only for updates
int store_type; // update only
int pos; // both
int id; // query
event(int tim, bool se, int tp, int p) {
time = tim;
type = 0;
start_or_end = se;
store_type = tp;
pos = p;
}
event(int tim, int p, int i) {
type = 1;
time = tim;
pos = p;
id = i;
}
};
bool operator<(event &a, event &b) {
return (a.time == b.time) ? (a.type < b.type) : (a.time < b.time);
}
vector<event> events;
int answs[MAXN];
int cnt[MAXN];
int num_active = 0;
multiset<int> locs[MAXN];
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
int mx[2];
multiset<int> all_vals[2]; // only for lowest level
stree(int lv, int rv) {
mx[0] = mx[1] = 0;
lp = lv;
rp = rv;
}
int mxq(int lv, int rv, bool lr) {
if (lp > rv || rp < lv) return 0;
if (lp >= lv && rp <= rv) return mx[lr];
int best = 0;
if (l) best = max(best, l->mxq(lv, rv, lr));
if (r) best = max(best, r->mxq(lv, rv, lr));
return best;
}
void update(int p, int v, bool lr) {
if (lp == rp) {
all_vals[lr].insert(v);
mx[lr] = *(all_vals[lr].rbegin());
return;
}
int m = (lp+rp)/2;
if (p <= m) {
if (!l) l = new stree(lp, m);
l->update(p, v, lr);
}
else {
if (!r) r = new stree(m+1, rp);
r->update(p, v, lr);
}
mx[lr] = 0;
if (l) mx[lr] = max(mx[lr], l->mx[lr]);
if (r) mx[lr] = max(mx[lr], r->mx[lr]);
}
void deupdate(int p, int v, bool lr) {
if (lp == rp) {
all_vals[lr].erase(all_vals[lr].find(v));
if (all_vals[lr].empty()) mx[lr] = 0;
else mx[lr] = *(all_vals[lr].rbegin());
return;
}
int m = (lp+rp)/2;
if (p <= m) {
if (!l) l = new stree(lp, m);
l->deupdate(p, v, lr);
}
else {
if (!r) r = new stree(m+1, rp);
r->deupdate(p, v, lr);
}
mx[lr] = 0;
if (l) mx[lr] = max(mx[lr], l->mx[lr]);
if (r) mx[lr] = max(mx[lr], r->mx[lr]);
}
};
stree *tree;
void make(int l, int r) {
if (l == -1 && r == -1) return;
if (l == -1) {
tree->update(0, r, 0);
return;
}
if (r == -1) {
tree->update(MAXV, MAXV-l, 1);
return;
}
int p1 = (l+r)/2;
int p2 = (l+r+1)/2;
int v1 = MAXV-l;
int v2 = r;
tree->update(p2, v2, 0);
tree->update(p1, v1, 1);
}
void unmake(int l, int r) {
if (l == -1 && r == -1) return;
if (l == -1) {
tree->deupdate(0, r, 0);
return;
}
if (r == -1) {
tree->deupdate(MAXV, MAXV-l, 1);
return;
}
int p1 = (l+r)/2;
int p2 = (l+r+1)/2;
int v1 = MAXV-l;
int v2 = r;
tree->deupdate(p2, v2, 0);
tree->deupdate(p1, v1, 1);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k >> q;
tree = new stree(0, MAXV);
for (int i = 0; i < n; i++) {
int x, t, a, b;
cin >> x >> t >> a >> b; t--;
events.push_back(event(a, 0, t, x));
events.push_back(event(b+1, 1, t, x));
}
for (int i = 0; i < q; i++) {
int x, t; cin >> x >> t;
events.push_back(event(t, x, i));
}
sort(events.begin(), events.end());
for (event ev: events) {
if (ev.type == 0) {
int type = ev.store_type;
if (ev.start_or_end == 0) {
num_active += (cnt[type] == 0);
cnt[type]++;
if (locs[type].find(ev.pos) != locs[type].end()) {
locs[type].insert(ev.pos);
continue;
}
auto iter = locs[type].lower_bound(ev.pos);
int r = -1;
int l = -1;
if (iter != locs[type].end()) r = *iter;
if (iter != locs[type].begin()) {
iter--;
l = *iter;
}
unmake(l, r);
locs[type].insert(ev.pos);
make(l, ev.pos);
make(ev.pos, r);
}
else {
cnt[type]--;
num_active -= (cnt[type] == 0);
locs[type].erase(locs[type].find(ev.pos));
if (locs[type].find(ev.pos) != locs[type].end()) continue;
auto iter = locs[type].lower_bound(ev.pos);
int r = -1;
int l = -1;
if (iter != locs[type].end()) r = *iter;
if (iter != locs[type].begin()) {
iter--;
l = *iter;
}
make(l, r);
unmake(l, ev.pos);
unmake(ev.pos, r);
}
}
if (ev.type == 1) {
if (num_active < k) {
answs[ev.id] = -1;
continue;
}
answs[ev.id] = max(tree->mxq(0, ev.pos, 0)-ev.pos, tree->mxq(ev.pos, MAXV, 1)-MAXV+ev.pos);
}
}
for (int i = 0; i < q; i++) cout << answs[i] << "\n";
}
