#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int SZ = 1 << 20;
int P[SZ], S[SZ], X[SZ], ans[SZ];
multiset<int> CX[SZ];
struct Seg {
priority_queue<int> T[SZ << 1], E[SZ << 1];
int CL[SZ << 1], CR[SZ << 1];
void Update(int L, int R, int v, bool e, int sL = 1, int sR = SZ, int n = 1) {
if (R < sL || sR < L) return;
if (L <= sL && sR <= R) {
(e ? E[n] : T[n]).push(v);
return;
}
int mid = (sL + sR) >> 1;
Update(L, R, v, e, sL, mid, n * 2);
Update(L, R, v, e, mid + 1, sR, n * 2 + 1);
}
int Query(int p) {
int sL = 1, sR = SZ, n = 1, ret = -1e9;
while (1) {
while (!T[n].empty() && !E[n].empty() && T[n].top() == E[n].top()) T[n].pop(), E[n].pop();
if (!T[n].empty()) ret = max(ret, T[n].top());
if (sL == sR) return ret;
int mid = (sL + sR) >> 1;
if (p <= mid) sR = mid, n = n * 2;
else sL = mid + 1, n = n * 2 + 1;
}
}
} T1, T2;
vector<int> UX;
int Find(int x) {
return lower_bound(UX.begin(), UX.end(), x) - UX.begin();
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, K, Q;
cin >> N >> K >> Q;
vector<pii> ord;
for (int i = 1; i <= N; ++i) {
int a, b;
cin >> P[i] >> S[i] >> a >> b;
P[i] <<= 1;
ord.emplace_back(a, i);
ord.emplace_back(b + 1, -i);
}
for (int i = 1; i <= Q; ++i) {
int t;
cin >> X[i] >> t;
X[i] <<= 1;
ord.emplace_back(t, SZ + i);
}
sort(ord.begin(), ord.end());
UX.push_back(-1); UX.push_back(1); UX.push_back(1e8);
for (auto [_, id] : ord) {
// Line Add
if (0 < id && id < SZ) {
int pos = P[abs(id)], type = S[abs(id)];
UX.push_back(pos);
auto it = CX[type].insert(pos);
if (it != CX[type].begin()) {
int h = abs(pos - *prev(it)) / 2;
UX.push_back(*prev(it) + h);
}
if (next(it) != CX[type].end()) {
int h = abs(pos - *next(it)) / 2;
UX.push_back(pos + h);
}
}
// Line Erase
else if (id < 0) {
int pos = P[abs(id)], type = S[abs(id)];
auto it = CX[type].find(pos);
if (it != CX[type].begin() && next(it) != CX[type].end()) {
int h = abs(*next(it) - *prev(it)) / 2;
UX.push_back(*prev(it) + h);
}
CX[type].erase(it);
}
else UX.push_back(X[id - SZ]);
}
sort(UX.begin(), UX.end());
UX.erase(unique(UX.begin(), UX.end()), UX.end());
memset(ans, 0xf3, sizeof(ans));
int curOpen = 0, L_LIM = 1, R_LIM = UX.size() - 1;
for (auto [_, id] : ord) {
// Line Add/Erase
if (id < SZ) {
int pos = P[abs(id)], type = S[abs(id)], x = Find(pos);
bool out = id < 0;
if (CX[type].empty()) curOpen++;
auto it = (out ? CX[type].find(pos) : CX[type].insert(pos));
bool isPrev = it != CX[type].begin();
bool isNext = next(it) != CX[type].end();
int ph = (isPrev ? Find(pos - (pos - *prev(it)) / 2) : L_LIM);
int nh = (isNext ? Find(pos + (*next(it) - pos) / 2) : R_LIM);
int all = (isPrev && isNext ? Find(*next(it) - (*next(it) - *prev(it)) / 2) : 0);
// Add
T2.Update(ph, x, pos, out);
T1.Update(x, nh, -pos, out);
// Modify
if (isNext) {
int nx = Find(*next(it));
T2.Update(isPrev ? all : L_LIM, nx, *next(it), !out);
T2.Update(nh, nx, *next(it), out);
}
if (isPrev) {
int px = Find(*prev(it));
T1.Update(px, isNext ? all : R_LIM, -*prev(it), !out);
T1.Update(px, ph, -*prev(it), out);
}
if (out) CX[type].erase(it);
if (CX[type].empty()) curOpen--;
}
// Query
else if (curOpen == K) {
id -= SZ;
int x = X[id], p = Find(x);
int b1 = T1.Query(p);
int b2 = T2.Query(p);
ans[id] = max(x + b1, b2 - x);
}
}
for (int i = 1; i <= Q; ++i) cout << (ans[i] < 0 ? -1 : ans[i] / 2) << '\n';
return 0;
}
