#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr int inf = 1000000100;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
struct PriqueErase {
priority_queue<int, vector<int>, greater<int>> a, b;
void push(int x) { a.push(x); }
void erase(int x) { b.push(x); }
int top() {
while (not a.empty()) {
const int v = a.top();
if (b.empty()) {
return v;
} else if (v == b.top()) {
a.pop();
b.pop();
} else {
return v;
}
}
return inf;
}
bool empty() {
while (not a.empty()) {
const int v = a.top();
if (b.empty()) {
return false;
} else if (v == b.top()) {
a.pop();
b.pop();
} else {
return false;
}
}
return a.empty();
}
};
int cnt_sp[2000000];
struct RIEPM {
int n, siz;
vector<PriqueErase> data;
vector<int> node;
RIEPM(int n_) : n(n_) {
data.assign(n, PriqueErase());
siz = 1;
while (siz < n) siz <<= 1;
node.assign(2 * siz, inf);
}
void push(int l, int r) {
assert(0 <= l and l <= r and r <= n);
--r;
data[r].push(l);
const int v = data[r].top();
r += siz;
node[r] = v;
while (r != 1) {
r >>= 1;
node[r] = min(node[2 * r], node[2 * r + 1]);
}
}
void erase(int l, int r) {
assert(0 <= l and l <= r and r <= n);
--r;
data[r].erase(l);
const int v = data[r].empty() ? inf : data[r].top();
r += siz;
node[r] = v;
while (r != 1) {
r >>= 1;
node[r] = min(node[2 * r], node[2 * r + 1]);
}
}
int fold(int l, int r) {
int res = inf;
for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = min(res, node[l++]);
if (r & 1) res = min(res, node[--r]);
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
fill(cnt_sp, cnt_sp + 2000000, 0);
int N, K, Q;
cin >> N >> K >> Q;
vector<int> X(N), T(N), A(N), B(N);
REP(i, N) {
cin >> X[i] >> T[i] >> A[i] >> B[i];
--T[i];
}
vector<int> L(Q), Y(Q);
REP(i, Q) cin >> L[i] >> Y[i];
auto reverse_points = [&]() {
REP(i, N) X[i] = inf - X[i];
REP(i, Q) L[i] = inf - L[i];
};
auto solve = [&]() {
vector<int> press;
REP(i, N) press.push_back(X[i]);
REP(i, Q) press.push_back(L[i]);
sort(ALL(press));
press.erase(unique(ALL(press)), press.end());
auto get_key = [&](int i) { return (int)(lower_bound(ALL(press), i) - press.begin()); };
const int M = (int)press.size();
RIEPM hp(M);
vector<tuple<int, int, int, int>> event;
REP(i, N) {
event.push_back({A[i], 0, X[i], T[i]});
event.push_back({B[i] + 1, 1, X[i], T[i]});
}
REP(i, Q) event.push_back({Y[i], 2, L[i], i});
sort(ALL(event));
vector<map<int, int>> pd(K);
vector<int> res(Q, -1);
int cnt_zero = K;
for (const auto &[c, qt, p, i] : event) {
if (qt == 0) {
if (pd[i].empty()) --cnt_zero;
auto [itr, vld] = pd[i].insert({p, 1});
if (not vld) {
++itr->second;
continue;
}
auto itr_r = itr;
++itr_r;
if (itr_r == pd[i].end()) {
hp.push(get_key(p), M);
} else {
hp.push(get_key(p), get_key((p + itr_r->first + 2) / 2));
}
if (itr == pd[i].begin()) continue;
auto itr_l = itr;
--itr_l;
const int l_id = get_key(itr_l->first);
hp.push(l_id, get_key((itr_l->first + p + 2) / 2));
if (itr_r != pd[i].end()) {
hp.erase(l_id, get_key((itr_l->first + itr_r->first + 2) / 2));
} else {
hp.erase(l_id, M);
}
}
if (qt == 1) {
auto itr = pd[i].find(p);
if (--(itr->second) != 0) {
continue;
}
pd[i].erase(p);
if (pd[i].empty()) ++cnt_zero;
auto itr_r = pd[i].upper_bound(p);
if (itr_r != pd[i].end()) {
hp.erase(get_key(p), get_key((p + itr_r->first + 2) / 2));
} else {
hp.erase(get_key(p), M);
}
if (itr_r == pd[i].begin()) continue;
auto itr_l = itr_r;
--itr_l;
const int l_id = get_key(itr_l->first);
hp.erase(l_id, get_key((itr_l->first + p + 2) / 2));
if (itr_r != pd[i].end()) {
hp.push(l_id, get_key((itr_l->first + itr_r->first + 2) / 2));
} else {
hp.push(l_id, M);
}
}
if (qt == 2) {
if (cnt_zero != 0) continue;
const int pi = get_key(p);
const int vi = hp.fold(pi, M);
if (vi == inf) continue;
res[i] = p - press[vi];
}
}
return res;
};
const auto res1 = solve();
reverse_points();
const auto res2 = solve();
REP(i, Q) {
const int ans = max(res1[i], res2[i]);
cout << ans << '\n';
}
}
