#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }
const int MAXN = 3e5 + 5;
int n, k, q, m;
vector<pair<int, int>> e;
pair<int, int> que[MAXN];
vector<int> comp;
array<int, 4> store[MAXN];
int ans[MAXN];
set<int> pos[MAXN];
multiset<int> val[MAXN];
int cnt[MAXN];
map<pair<int, int>, int> mp;
int st[MAXN * 4];
void upd(int p, int v) {
int l = 0, r = m, id = 1;
while (l < r) {
int mid = (l + r) >> 1;
if (mid >= p) r = mid, id = id << 1;
else l = mid + 1, id = id << 1 | 1;
}
if (v > 0) {
val[p].emplace(v);
st[id] = *val[p].rbegin();
} else {
v = -v;
val[p].erase(val[p].find(v));
st[id] = val[p].size() ? *val[p].rbegin() : -1;
}
while (id > 0) {
id >>= 1;
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
}
int get(int id, int l, int r, int u, int v) {
if (v < l || r < u) return -1;
if (u <= l && r <= v) return st[id];
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
int main() {
#define NAME "test"
if (fopen("test.inp", "r")) {
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
int x, t, a, b; cin >> x >> t >> a >> b;
store[i] = {x, t, a, b};
comp.emplace_back(x);
e.emplace_back(a, i);
e.emplace_back(b + 1, -i);
}
sort(comp.begin(), comp.end());
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
for (int i = 1; i <= q; i++) {
cin >> que[i].fi >> que[i].se;
e.emplace_back(que[i].se, i + n);
}
sort(e.begin(), e.end());
for (int i = 1; i <= n; i++) {
store[i][0] = lower_bound(comp.begin(), comp.end(), store[i][0]) - comp.begin() + 1;
}
m = comp.size();
memset(st, -1, sizeof st);
for (int i = 1; i <= k; i++) {
pos[i].emplace(0);
pos[i].emplace(m + 1);
upd(0, m + 1);
}
for (auto [tim, id] : e) {
if (id <= n) {
auto [x, t, a, b] = store[abs(id)];
if (id > 0) {
mp[{t, x}]++;
if (mp[{t, x}] == 1) {
auto it = pos[t].insert(x).fi;
auto prv = prev(it);
auto nxt = next(it);
upd(*prv, -*nxt);
upd(*prv, *it);
upd(*it, *nxt);
}
} else {
mp[{t, x}]--;
if (mp[{t, x}] == 0) {
auto it = pos[t].find(x);
auto prv = prev(it);
auto nxt = next(it);
upd(*it, -*nxt);
upd(*prv, -*it);
upd(*prv, *nxt);
pos[t].erase(it);
}
}
} else {
id -= n;
int l = 0, r = 1e8; ans[id] = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int le = lower_bound(comp.begin(), comp.end(), que[id].fi - mid) - comp.begin() + 1;
int ri = upper_bound(comp.begin(), comp.end(), que[id].fi + mid) - comp.begin();
if (get(1, 0, m, 0, le - 1) <= ri) r = mid - 1, ans[id] = mid;
else l = mid + 1;
}
}
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;
}
