#include <bits/stdc++.h>
#define nl '\n'
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
struct SegmentTree {
int n;
std::vector<int> t;
SegmentTree(int _n) : n(_n), t(2 * n, -1) {}
void update(int p, int v) {
for (t[p += n] = v; p > 1; p >>= 1) {
t[p >> 1] = std::max(t[p], t[p ^ 1]);
}
}
int query(int l, int r) {
int ans = -1;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = std::max(ans, t[l++]);
if (r & 1) ans = std::max(ans, t[--r]);
}
return ans;
}
};
struct Store {
int x, t, a, b;
bool operator<(const Store& rhs) const {
return x < rhs.x;
}
};
struct Query {
int l, y;
};
struct Event {
int time, id;
bool operator<(const Event& rhs) const {
return std::make_pair(time, id) < std::make_pair(rhs.time, rhs.id);
}
};
bool operator<(const Store& s, const int& x) {
return s.x < x;
}
bool operator<(const int& x, const Store& s) {
return x < s.x;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k, q;
std::cin >> n >> k >> q;
std::vector<Store> stores(n + 1);
stores[0].x = -1;
for (int i = 0; i < n; i++) {
int x, t, a, b;
std::cin >> x >> t >> a >> b;
--t;
stores[i + 1] = {x, t, a, b};
}
std::sort(stores.begin() + 1, stores.end());
std::vector<int> ans(q);
std::vector<Query> queries(q);
for (int i = 0; i < q; i++) {
std::cin >> queries[i].l >> queries[i].y;
}
std::vector<Event> events;
for (int i = 1; i <= n; i++) {
events.push_back({stores[i].a, i});
events.push_back({stores[i].b + 1, i});
}
for (int i = 0; i < q; i++) {
events.push_back({queries[i].y, i + n + 1});
}
std::sort(events.begin(), events.end());
std::vector<std::set<int>> pos(k);
std::vector<std::multiset<int>> at(n + 1);
for (int i = 0; i < k; i++) {
at[0].insert(n + 1);
pos[i].insert(0);
pos[i].insert(n + 1);
}
dbg("goes here");
SegmentTree tree(n + 1);
tree.update(0, n + 1);
auto rem_at = [&](int id, int v) {
at[id].erase(at[id].find(v));
tree.update(id, at[id].empty() ? -1 : *at[id].rbegin());
};
auto add_at = [&](int id, int v) {
at[id].insert(v);
tree.update(id, at[id].empty() ? -1 : *at[id].rbegin());
};
for (auto [time, id] : events) {
dbg(time, id);
if (id <= n) {
auto [x, t, a, b] = stores[id];
if (time == a) {
dbg("goes insert", time, id);
dbg(pos[t], t);
auto it = pos[t].insert(id).first;
auto pre = std::prev(it);
auto nxt = std::next(it);
dbg(*it, *pre, *nxt);
rem_at(*pre, *nxt);
add_at(*pre, *it);
add_at(*it, *nxt);
} else {
auto it = pos[t].find(id);
auto pre = std::prev(it);
auto nxt = std::next(it);
rem_at(*it, *nxt);
rem_at(*pre, *it);
add_at(*pre, *nxt);
pos[t].erase(it);
}
} else {
id -= n + 1;
int res = -1;
int lb = 0, rb = 1e8;
while (lb <= rb) {
int mb = (lb + rb) / 2;
int ql = std::lower_bound(stores.begin() + 1, stores.end(), queries[id].l - mb) - stores.begin();
int qr = std::upper_bound(stores.begin() + 1, stores.end(), queries[id].l + mb) - stores.begin();
if (tree.query(0, ql) < qr) {
res = mb;
rb = mb - 1;
} else {
lb = mb + 1;
}
}
ans[id] = res;
}
}
for (int i = 0; i < q; i++) {
std::cout << ans[i] << nl;
}
}
