#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define inline inline __attribute__((always_inline))
using namespace std;
constexpr int N = 3e5 + 5;
constexpr int INF = 1e9;
struct Store {
int x, type, l, r;
};
Store stores[N];
vector<int> positions[N];
int xoi[N];
int toi[N];
pair<int, int> real_queries[N];
vector<pair<int, int>> queries[N];
vector<pair<int, bool>> updates[N];
// sexagesicuaternary tree
class FastSet {
using u64 = unsigned long long;
int n;
vector<vector<u64>> tree;
public:
void assign(int n) {
this->n = n;
tree.clear();
if (n == 0) return;
int sz = n;
while (true) {
int new_sz = (sz + 63) >> 6;
tree.emplace_back(new_sz, 0ull); // empty set
if (new_sz == 1) break;
sz = new_sz;
}
}
void insert(int i) {
if (i < 0 || i >= n) return;
for (size_t h = 0; h < tree.size(); h++) {
u64 mask = 1ull << (i & 63);
if (tree[h][i >> 6] & mask) break;
tree[h][i >> 6] |= mask;
i >>= 6;
}
}
void erase(int i) {
if (i < 0 || i >= n) return;
for (size_t h = 0; h < tree.size(); h++) {
tree[h][i >> 6] &= ~(1ull << (i & 63));
if (tree[h][i >> 6]) break;
i >>= 6;
}
}
inline void set(int i, bool value) {
if (value)
insert(i);
else
erase(i);
}
// lower_bound
int next(int i) const {
for (size_t h = 0; h < tree.size(); h++) {
int u = i >> 6;
if (u >= tree[h].size()) break;
u64 mask = tree[h][u] & (~0ull << (i & 63));
if (!mask) {
i = (i >> 6) + 1;
continue;
}
i = (u << 6) + __builtin_ctzll(mask);
for (int g = (int)h - 1; g >= 0; g--) {
i = (i << 6) + __builtin_ctzll(tree[g][i]);
}
return (i < n) ? i : n;
}
return n;
}
// --upper_bound
int prev(int i) const {
for (size_t h = 0; h < tree.size(); h++) {
int u = i >> 6;
if (u < 0) break;
u64 mask = tree[h][u];
if ((i & 63) != 63) {
mask &= (1ull << ((i & 63) + 1)) - 1;
}
if (!mask) {
i = (i >> 6) - 1;
continue;
}
i = (u << 6) + (63 - __builtin_clzll(mask));
for (int g = (int)h - 1; g >= 0; g--) {
i = (i << 6) + (63 - __builtin_clzll(tree[g][i]));
}
return i;
}
return -1;
}
inline bool operator[](int i) const {
return (tree[0][i >> 6] >> (i & 63)) & 1;
}
inline int size() const {
return n;
}
};
FastSet fs[N];
struct SegmentTree {
int n;
int tree[N * 2];
struct DEPQ {
priority_queue<int> pq;
priority_queue<int> to_delete;
int query() {
while (!to_delete.empty() && to_delete.top() == pq.top()) {
to_delete.pop();
pq.pop();
}
return pq.empty() ? -INF : pq.top();
}
void insert(int value) {
pq.push(value);
}
void erase(int value) {
to_delete.push(value);
}
} leaves[N];
void init(int n) {
this->n = n;
fill(tree + 1, tree + 2 * n, -INF);
}
inline void build(int i) {
int value = leaves[i].query();
for (tree[i += n] = value; i > 1; i >>= 1) {
tree[i >> 1] = max(tree[i], tree[i ^ 1]);
}
}
inline void insert(int i, int value) {
leaves[i].insert(value);
build(i);
}
inline void erase(int i, int value) {
leaves[i].erase(value);
build(i);
}
inline int query(int l, int r) {
int res = -INF;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, tree[l++]);
if (r & 1) res = max(res, tree[--r]);
}
return res;
}
} Ltree, Rtree;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
int n, k, q;
cin >> n >> k >> q;
for (int i = 0; i < n; i++) {
auto &[x, type, l, r] = stores[i];
cin >> x >> type >> l >> r;
}
sort(stores, stores + n, [](const Store &s, const Store &t) {
return s.x < t.x;
});
for (int i = 0; i < n; i++) {
positions[stores[i].type].push_back(i);
}
for (int i = 0; i < q; i++) {
auto &[x, t] = real_queries[i];
cin >> x >> t;
xoi[i] = x;
toi[i] = t;
}
sort(xoi, xoi + q);
int X = unique(xoi, xoi + q) - xoi;
sort(toi, toi + q);
int T = unique(toi, toi + q) - toi;
for (int i = 0; i < q; i++) {
auto [x, t] = real_queries[i];
x = lower_bound(xoi, xoi + X, x) - xoi;
t = lower_bound(toi, toi + T, t) - toi;
queries[t].emplace_back(x, i);
}
for (int i = 0; i < n; i++) {
auto [x, type, l, r] = stores[i];
l = lower_bound(toi, toi + T, l) - toi;
r = upper_bound(toi, toi + T, r) - toi;
updates[l].emplace_back(i, true);
updates[r].emplace_back(i, false);
}
for (int type = 1; type <= k; type++) {
for (int it = 0; it < positions[type].size(); it++) {
int i = positions[type][it];
stores[i].l = it;
}
}
Ltree.init(X + 1);
Rtree.init(X + 1);
for (int t = 1; t <= k; t++) {
Ltree.insert(0, INF);
Rtree.insert(0, INF);
}
for (int type = 1; type <= k; type++) {
fs[type].assign(positions[type].size());
}
auto insert_store = [&](int type, int pos) {
int x = stores[positions[type][pos]].x;
int L = fs[type].prev(pos);
int R = fs[type].next(pos);
L = L < 0 ? -INF : stores[positions[type][L]].x;
R = R >= fs[type].size() ? INF : stores[positions[type][R]].x;
int M = upper_bound(xoi, xoi + X, (L + R) / 2) - xoi;
int Ml = upper_bound(xoi, xoi + X, (L + x) / 2) - xoi;
int Mr = upper_bound(xoi, xoi + X, (x + R) / 2) - xoi;
Ltree.erase(M, -L);
Rtree.erase(M, R);
Ltree.insert(Ml, -L);
Rtree.insert(Ml, x);
Ltree.insert(Mr, -x);
Rtree.insert(Mr, R);
fs[type].insert(pos);
};
auto erase_store = [&](int type, int pos) {
int x = stores[positions[type][pos]].x;
fs[type].erase(pos);
int L = fs[type].prev(pos);
int R = fs[type].next(pos);
L = L < 0 ? -INF : stores[positions[type][L]].x;
R = R >= fs[type].size() ? INF : stores[positions[type][R]].x;
int M = upper_bound(xoi, xoi + X, (L + R) / 2) - xoi;
int Ml = upper_bound(xoi, xoi + X, (L + x) / 2) - xoi;
int Mr = upper_bound(xoi, xoi + X, (x + R) / 2) - xoi;
Ltree.erase(Ml, -L);
Rtree.erase(Ml, x);
Ltree.erase(Mr, -x);
Rtree.erase(Mr, R);
Ltree.insert(M, -L);
Rtree.insert(M, R);
};
for (int t = 0; t <= T; t++) {
for (auto [i, insert] : updates[t]) {
auto [x, type, l, r] = stores[i];
if (insert) {
insert_store(type, l);
} else {
erase_store(type, l);
}
}
for (auto [Xmap, i] : queries[t]) {
int x = xoi[Xmap];
int &ans = real_queries[i].first;
ans = max(Ltree.query(Xmap + 1, X + 1) + x,
Rtree.query(0, Xmap + 1) - x);
}
}
for (int t = T - 1; t >= 0; t--) {
for (auto it = updates[t + 1].rbegin(); it != updates[t + 1].rend(); ++it) {
auto [i, erase] = *it;
auto [x, type, l, r] = stores[i];
if (erase) {
erase_store(type, l);
} else {
insert_store(type, l);
}
}
for (auto [Xmap, i] : queries[t]) {
int x = xoi[Xmap];
int &ans = real_queries[i].first;
ans = max(ans,
max(Ltree.query(Xmap + 1, X + 1) + x,
Rtree.query(0, Xmap + 1) - x));
}
}
for (int i = 0; i < q; i++) {
int ans = real_queries[i].first;
cout << (ans >= (int)1e8 ? -1 : ans) << '\n';
}
return 0;
}
