#include <iostream>
#include <vector>
#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> queries[N];
vector<pair<int, int>> queries_at[N];
vector<int> lstores[N];
vector<int> rstores[N];
// sexagesicuaternary tree
class FastSet {
using u64 = unsigned long long;
int n;
vector<vector<u64>> tree;
public:
void assign(int n) {
int sz = this->n = n;
tree.clear();
while (true) {
int new_sz = (sz + 63) >> 6;
tree.emplace_back(new_sz, ~0ull); // full set
if (new_sz == 1) break;
sz = new_sz;
}
if (n & 63 == 0) return;
tree[0].back() &= (1ull << (n & 63)) - 1;
int u = n >> 6;
for (size_t h = 0; h < tree.size() - 1; h++) {
if (tree[h][u]) break;
int p = u >> 6;
tree[h + 1][p] &= ~(1ull << (u & 63));
u = p;
}
}
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;
}
}
// lower_bound
int next(int i) const {
if (i >= n) return n;
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 size_t size() const {
return n;
}
};
FastSet fs[N];
struct SegmentTree {
struct Node {
int max;
int lazy;
inline void apply(int chmax) {
max = std::max(max, chmax);
lazy = std::max(lazy, chmax);
}
inline void push(Node &left, Node &right) {
if (lazy == -INF) return;
left.apply(lazy);
right.apply(lazy);
lazy = -INF;
}
inline void pull(const Node &left, const Node &right) {
max = std::max(left.max, right.max);
}
} tree[4 * N];
void update(int id, int l, int r, int u, int v, int chmax) {
if (l >= v || r <= u) return;
if (u <= l && r <= v) {
tree[id].apply(chmax);
return;
}
int m = l + r >> 1;
tree[id].push(tree[id * 2], tree[id * 2 + 1]);
update(id * 2, l, m, u, v, chmax);
update(id * 2 + 1, m, r, u, v, chmax);
}
int query(int id, int l, int r, int u) {
if (l + 1 == r) return tree[id].max;
int m = l + r >> 1;
tree[id].push(tree[id * 2], tree[id * 2 + 1]);
if (u < m)
return query(id * 2, l, m, u);
return query(id * 2 + 1, m, r, u);
}
void build(int id, int l, int r) {
tree[id].max = tree[id].lazy = -INF;
if (l + 1 == r) {
return;
}
int m = l + r >> 1;
build(id * 2, l, m);
build(id * 2 + 1, m, r);
}
} 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] = 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] = queries[i];
x = lower_bound(xoi, xoi + X, x) - xoi;
t = lower_bound(toi, toi + T, t) - toi;
queries_at[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;
lstores[l].push_back(i);
rstores[r].push_back(i);
}
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;
}
}
auto reset = [&]() {
Ltree.build(1, 0, X);
Rtree.build(1, 0, X);
for (int type = 1; type <= k; type++) {
fs[type].assign(positions[type].size());
// cout << "f_" << type << "(x) = \\left\\{";
int L = -INF;
int Lmap = 0;
for (int i : positions[type]) {
int R = stores[i].x;
int Rmap = lower_bound(xoi, xoi + X, R) - xoi;
int Mmap = lower_bound(xoi, xoi + X, (L + R + 1) / 2) - xoi;
// cout << L << " <= x < " << (L + R) * 0.5 << ": x - " << L << ", ";
// cout << (L + R) * 0.5 << " <= x < " << R << ": " << R << " - x, ";
Ltree.update(1, 0, X, Lmap, Mmap, -L);
Rtree.update(1, 0, X, Mmap, Rmap, R);
L = R;
Lmap = Rmap;
}
// cout << L << " <= x: x - " << L << "\\right\\}" << endl;
Ltree.update(1, 0, X, Lmap, X, -L);
}
};
auto erase = [&](int type, int pos) {
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 Lmap = lower_bound(xoi, xoi + X, L) - xoi;
int Mmap = lower_bound(xoi, xoi + X, (L + R + 1) / 2) - xoi;
int Rmap = lower_bound(xoi, xoi + X, R) - xoi;
// cout << "removed store type " << type << " at position " << x << ". Adjacent stores are " << L << " and " << R << endl;
// cout << "y = \\left\\{";
// cout << L << " <= x < " << (L + R) * 0.5 << ": x - " << L << ", ";
// cout << (L + R) * 0.5 << " <= x < " << R << ": " << R << " - x\\right\\}" << endl;
Ltree.update(1, 0, X, Lmap, Mmap, -L);
Rtree.update(1, 0, X, Mmap, Rmap, R);
};
// L-R
reset();
// for (int Xmap = 0; Xmap < X; Xmap++) {
// int x = xoi[Xmap];
// cout << "f(" << x << ") = " << max(Ltree.query(1, 0, X, Xmap) + x,
// Rtree.query(1, 0, X, Xmap) - x) << endl;
// }
for (int t = 0; t < T; t++) {
for (int i : rstores[t]) {
auto [x, type, l, r] = stores[i];
erase(type, l);
}
for (auto [Xmap, i] : queries_at[t]) {
int x = xoi[Xmap];
int &ans = queries[i].first;
ans = max(Ltree.query(1, 0, X, Xmap) + x,
Rtree.query(1, 0, X, Xmap) - x);
}
}
// R-L
reset();
for (int t = T - 1; t >= 0; t--) {
for (int i : lstores[t + 1]) {
auto [x, type, l, r] = stores[i];
erase(type, l);
}
for (auto [Xmap, i] : queries_at[t]) {
int x = xoi[Xmap];
int &ans = queries[i].first;
ans = max(ans,
max(Ltree.query(1, 0, X, Xmap) + x,
Rtree.query(1, 0, X, Xmap) - x));
}
}
for (int i = 0; i < q; i++) {
int ans = queries[i].first;
cout << (ans > (int)1e8 ? -1 : ans) << '\n';
}
return 0;
}
