#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l + r) >> 1)
const int N = 300'005;
struct segtree {
set<array<int, 3>> seg[1 << 20];
void insert(int i, int l, int r, int s, int e, array<int, 3> v) {
if (s <= l && r <= e) {
seg[i].insert(v);
return;
}
if (r < s || e < l) {
return;
}
insert(i << 1, l, mid, s, e, v);
insert(i << 1 | 1, mid + 1, r, s, e, v);
}
void erase(int i, int l, int r, int s, int e, array<int, 3> v) {
if (s <= l && r <= e) {
seg[i].erase(v);
return;
}
if (r < s || e < l) {
return;
}
erase(i << 1, l, mid, s, e, v);
erase(i << 1 | 1, mid + 1, r, s, e, v);
}
void get(int i, int l, int r, int x, int xv, int &mx, int &cnt) {
if (seg[i].size()) {
mx = max(mx, abs(xv - (*seg[i].rbegin())[0]));
mx = max(mx, abs(xv - (*seg[i].begin())[0]));
cnt += seg[i].size();
}
if (l == r) {
return;
}
if (x <= mid) {
get(i << 1, l, mid, x, xv, mx, cnt);
} else {
get(i << 1 | 1, mid + 1, r, x, xv, mx, cnt);
}
}
} seg;
multiset<array<int, 2>> pos[N];
vector<array<int, 2>> ask[N];
vector<array<int, 3>> in[N], out[N];
array<int, 2> cur[N];
int ans[N];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, k, q;
cin >> n >> k >> q;
array<int, 4> a[n];
for (int i = 0; i < n; i++) {
cur[i] = {-1, -2};
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
}
array<int, 2> qq[q];
vector<int> v1, v2;
for (int i = 0; i < q; i++) {
cin >> qq[i][0] >> qq[i][1];
v1.push_back(qq[i][0]);
v2.push_back(qq[i][1]);
}
sort(v1.begin(), v1.end());
v1.resize(unique(v1.begin(), v1.end()) - v1.begin());
sort(v2.begin(), v2.end());
v2.resize(unique(v2.begin(), v2.end()) - v2.begin());
auto get = [&] (int s, int e, vector<int> &vv) {
int l = lower_bound(vv.begin(), vv.end(), s) - vv.begin();
int r = upper_bound(vv.begin(), vv.end(), e) - vv.begin() - 1;
return (array<int, 2>) {l, r};
};
auto get2 = [&] (int x, vector<int> &vv) {
return lower_bound(vv.begin(), vv.end(), x) - vv.begin();
};
for (int i = 0; i < n; i++) {
array<int, 2> v = get(a[i][2], a[i][3], v2);
if (v[0] > v[1]) continue;
in[v[0]].push_back({a[i][0], a[i][1], i});
out[v[1]].push_back({a[i][0], a[i][1], i});
}
for (int i = 0; i < q; i++) {
ask[get2(qq[i][1], v2)].push_back({qq[i][0], i});
}
auto update = [&] (int idx, int s, int e) {
// cout << idx << " -> " << s << ' ' << e << '\n';
if (cur[idx][0] <= cur[idx][1]) {
array<int, 2> v = get(cur[idx][0], cur[idx][1], v1);
if (v[0] <= v[1]) {
seg.erase(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {a[idx][0], a[idx][1], idx});
}
}
if (s == -1) {
cur[idx] = {-1, -2};
return void();
}
cur[idx] = {s, e};
array<int, 2> v = get(s, e, v1);
if (v[0] > v[1]) {
return void();
}
seg.insert(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {a[idx][0], a[idx][1], idx});
};
// auto insert = [&] (int s, int e, int val, int t, int idx) {
// array<int, 2> v = get(s, e, v1);
// if (v[0] > v[1]) return void();
// seg.insert(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {val, t, idx});
// };
// auto erase = [&] (int s, int e, int val, int t, int idx) {
// array<int, 2> v = get(s, e, v1);
// if (v[0] > v[1]) return void();
// seg.erase(1, 0, v1.size() - 1, v[0], v[1], (array<int, 3>) {val, t, idx});
// };
for (int i = 0; i < v2.size(); i++) {
for (auto [x, t, idx] : in[i]) {
pos[t].insert({x, idx});
auto it = pos[t].lower_bound({x, idx});
int l = 0, r = 1e8;
if (it != pos[t].begin()) {
it--;
array<int, 2> L = (*it);
int md = (L[0] + x) / 2;
it++;
it++;
int en = 1e8;
if (it != pos[t].end()) {
en = (L[0] + (*it)[0]) / 2;
}
it--;
update(L[1], cur[L[1]][0], md);
l = md + 1;
}
if ((++it) != pos[t].end()) {
array<int, 2> R = (*it);
int md = (x + R[0]) / 2;
it--;
int st = 0;
if (it != pos[t].begin()) {
it--;
st = ((*it)[0] + R[0]) / 2 + 1;
it++;
}
it++;
update(R[1], md + 1, cur[R[1]][1]);
r = md;
}
it--;
update(idx, l, r);
}
for (auto [x, idx] : ask[i]) {
// cout << "? " << x << " (" << idx << ")" << '\n';
int p = get2(x, v1);
int mx = 0, cnt = 0;
seg.get(1, 0, v1.size() - 1, p, x, mx, cnt);
if (cnt != k) {
ans[idx] = -1;
continue;
}
ans[idx] = mx;
}
for (auto [x, t, idx] : out[i]) {
update(idx, -1, -1);
auto it = pos[t].lower_bound({x, idx});
int l = 0, r = 1e8;
if (it != pos[t].begin()) {
it--;
array<int, 2> L = (*it);
int md = (L[0] + x) / 2;
it++;
it++;
int en = 1e8;
if (it != pos[t].end()) {
en = (L[0] + (*it)[0]) / 2;
}
it--;
update(L[1], cur[L[1]][0], en);
l = md + 1;
}
if ((++it) != pos[t].end()) {
array<int, 2> R = (*it);
int md = (x + R[0]) / 2;
it--;
int st = 0;
if (it != pos[t].begin()) {
it--;
st = ((*it)[0] + R[0]) / 2 + 1;
it++;
}
it++;
update(R[1], st, cur[R[1]][1]);
r = md;
}
it--;
pos[t].erase({x, idx});
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
