#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
const int M = 3e8 + 10;
int n, k, q;
multiset <int> s[N];
int ans[N];
int cnt;
vector <int> dta;
void fake_add(int t, int x) {
int L = *(--s[t].upper_bound(x));
int R = *s[t].upper_bound(x);
dta.push_back(L);
dta.push_back(R);
dta.push_back(x);
dta.push_back((L + R) / 2);
dta.push_back((L + x) / 2);
dta.push_back((x + R) / 2);
s[t].insert(x);
}
void fake_rev(int t, int x) {
s[t].erase(s[t].find(x));
int L = *(--s[t].upper_bound(x));
int R = *s[t].upper_bound(x);
dta.push_back(L);
dta.push_back(R);
dta.push_back(x);
dta.push_back((L + R) / 2);
dta.push_back((L + x) / 2);
dta.push_back((x + R) / 2);
}
map <pair <int, int>, vector <int> > id[N];
int ti;
struct __ {
int x, y, u, v, a, b;
};
vector <__> _;
vector <tuple <int, int, int, int> > work[N * 4];
void push(int id, int L, int R, int u, int v, int x, int y, int a, int b) {
if (u > R || L > v || u > v) return;
if (u <= L && R <= v) {
work[id].push_back({x, y, a, b});
return;
}
int mid = L + R >> 1;
push(id * 2, L, mid, u, v, x, y, a, b);
push(id * 2 + 1, mid + 1, R, u, v, x, y, a, b);
}
void add(int t, int X) {
cnt -= (s[t].size() == 2);
int L = *(--s[t].upper_bound(X));
int R = *s[t].upper_bound(X);
int l = lower_bound(dta.begin(), dta.end(), L) - dta.begin();
int r = lower_bound(dta.begin(), dta.end(), R) - dta.begin();
int lr = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
int i = id[t][{L, R}].back();
id[t][{L, R}].pop_back();
_.push_back({i, ti - 1, l, lr, 1, - L});
_.push_back({i, ti - 1, lr + 1, r, -1, R});
id[t][{L, X}].push_back(ti);
id[t][{X, R}].push_back(ti);
s[t].insert(X);
}
void rev(int t, int X) {
s[t].erase(s[t].find(X));
int L = *(--s[t].upper_bound(X));
int R = *s[t].upper_bound(X);
int l = lower_bound(dta.begin(), dta.end(), L) - dta.begin();
int r = lower_bound(dta.begin(), dta.end(), R) - dta.begin();
int x = lower_bound(dta.begin(), dta.end(), X) - dta.begin();
int lr = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
int lx = lower_bound(dta.begin(), dta.end(), (L + X) / 2) - dta.begin();
int rx = lower_bound(dta.begin(), dta.end(), (X + R) / 2) - dta.begin();
id[t][{L, R}].push_back(ti);
int i = id[t][{L, X}].back();
id[t][{L, X}].pop_back();
_.push_back({i, ti - 1, l, lx, 1, - L});
_.push_back({i, ti - 1, lx + 1, x, - 1, X});
i = id[t][{X, R}].back();
id[t][{X, R}].pop_back();
_.push_back({i, ti - 1, x, rx, 1, - X});
_.push_back({i, ti - 1, rx + 1, r, - 1, R});
cnt += (s[t].size() == 2);
}
struct SegmentTree {
vector <int> st[N * 20];
void add(int id, int L, int R, int u, int v, int val) {
if (u > R || L > v) return;
if (u <= L && R <= v) {
st[id].push_back((st[id].empty() ? val : max(val, st[id].back())));
return;
}
int mid = L + R >> 1;
add(id * 2, L, mid, u, v, val);
add(id * 2 + 1, mid + 1, R, u, v, val);
}
void rollback(int id, int L, int R, int u, int v) {
if (u > R || L > v) return;
if (u <= L && R <= v) {
st[id].pop_back();
return;
}
int mid = L + R >> 1;
rollback(id * 2, L, mid, u, v);
rollback(id * 2 + 1, mid + 1, R, u, v);
}
int get(int id, int L, int R, int i) {
int ans = (st[id].empty() ? - 1e9 : st[id].back());
if (L == R) return ans;
int mid = L + R >> 1;
if (i <= mid) return max(get(id * 2, L, mid, i), ans);
else return max(get(id * 2 + 1, mid + 1, R, i), ans);
}
} lft, rgt;
int ask[N], wh[N];
void solve(int id, int L, int R) {
for (auto [u, v, a, b]: work[id]) {
if (a < 0) lft.add(1, 0, dta.size() - 1, u, v, b);
else rgt.add(1, 0, dta.size() - 1, u, v, b);
}
if (L == R) {
if (wh[L]) {
ans[wh[L]] = max(- dta[ask[L]] + lft.get(1, 0, dta.size() - 1, ask[L]), dta[ask[L]] + rgt.get(1, 0, dta.size() - 1, ask[L]));
}
} else {
int mid = L + R >> 1;
solve(id * 2, L, mid);
solve(id * 2 + 1, mid + 1, R);
}
reverse(work[id].begin(), work[id].end());
for (auto [u, v, a, b]: work[id]) {
if (a < 0) lft.rollback(1, 0, dta.size() - 1, u, v);
else rgt.rollback(1, 0, dta.size() - 1, u, v);
}
}
int main() {
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
ios :: sync_with_stdio(0); cin.tie(0);
vector <tuple <int, int, int, int> > events;
cin >> n >> k >> q;
for (int i = 0; i < n; ++i) {
int x, t, a, b;
cin >> x >> t >> a >> b;
x += 1e8 + 5;
events.push_back({a, -1, x, t});
events.push_back({b + 1, 1, x, t});
}
sort(events.begin(), events.end());
for (int i = 1; i <= k; ++i) {
s[i].insert(0), s[i].insert(M);
int L = 0, R = M;
dta.push_back(L), dta.push_back(R);
dta.push_back((L + R) / 2);
}
for (auto [_, cmd, x, t]: events) {
if (cmd == -1) fake_add(t, x);
else fake_rev(t, x);
}
cnt = k;
vector <tuple <int, int, int> > work;
for (int i = 1; i <= q; ++i) {
int x, y;
cin >> x >> y;
x += 1e8 + 5;
work.push_back({y, x, i});
dta.push_back(x);
}
sort(work.begin(), work.end());
sort(dta.begin(), dta.end());
dta.erase(unique(dta.begin(), dta.end()), dta.end());
for (int i = 1; i <= k; ++i) {
int L = 0, R = M;
id[i][{L, R}].push_back(1);
}
int i = 0;
for (auto [y, x, id]: work) {
++ti;
while (i < events.size() && get<0>(events[i]) <= y) {
auto [_, cmd, x, t] = events[i];
if (cmd == -1) add(t, x);
else rev(t, x);
++i;
}
x = lower_bound(dta.begin(), dta.end(), x) - dta.begin();
ask[ti] = x;
wh[ti] = id;
if (cnt) ans[id] = -1, ask[ti] = 0, wh[ti] = 0;
}
++ti;
while (i < events.size()) {
auto [_, cmd, x, t] = events[i];
if (cmd == -1) add(t, x);
else rev(t, x);
++i;
}
for (int i = 1; i <= k; ++i) {
int L = 0, R = M;
int l = 0, r = dta.size() - 1;
int m = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
int _i = id[i][{L, R}].back();
id[i][{L, R}].pop_back();
_.push_back({_i, ti - 1, l, m, 1, -L});
_.push_back({_i, ti - 1, m + 1, r, -1, L});
}
for (auto [L, R, u, v, a, b]: _)
push(1, 1, ti, L, R, u, v, a, b);
solve(1, 1, ti);
for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
