#include <bits/stdc++.h>
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
using namespace std;
struct E {
int p, t, x, y;
};
const int N = 12e4 + 5, INF = 1e9;
vector<int> vx;
multiset<int> occ[N], t[N];
int n, q, k, cc;
int ans[N];
struct ST {
vector<int> up[N * 4];
multiset<int> t[N];
void push(int v, int L, int R) {
if (!up[v].empty()) {
if (L != R) {
up[v * 2].insert(up[v * 2].end(), all(up[v]));
up[v * 2 + 1].insert(up[v * 2 + 1].end(), all(up[v]));
}
else {
for (int x : up[v]) {
if (x < 0) {
t[L].erase(t[L].find(-x));
}
else {
t[L].insert(x);
}
}
}
up[v].clear();
}
}
void upd(int l, int r, int x, int v, int L, int R) {
if (l > r)
return;
if (l == L && r == R) {
up[v].push_back(x);
}
else {
push(v, L, R);
int m = (L + R) >> 1;
upd(l, min(m, r), x, v * 2, L, m);
upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
}
}
} segt[2];
int que(int x, int v, int L, int R, ST &a, ST &b) {
a.push(v, L, R);
b.push(v, L, R);
if (L == R) {
if (a.t[L].size() + b.t[L].size() < k)
return -1;
int ans = 0;
if (!a.t[L].empty())
ans = max(ans, vx[L] - *a.t[L].begin());
if (!b.t[L].empty())
ans = max(ans, *b.t[L].rbegin() - vx[L]);
return ans;
}
int m = (L + R) >> 1;
if (x <= m)
return que(x, v * 2, L, m, a, b);
return que(x, v * 2 + 1, m + 1, R, a, b);
}
void updBetween(int x, int y, int k) {
if (x == y)
return;
// cout << "BET " << x << " " << y << " " << k << "\n";
int m = (x + y) / 2,
m1 = upper_bound(all(vx), m) - vx.begin(),
x1 = lower_bound(all(vx), x) - vx.begin(),
y1 = lower_bound(all(vx), y) - vx.begin();
segt[0].upd(x1, m1 - 1, k * x, 1, 0, cc - 1);
segt[1].upd(m1, y1 - 1, k * y, 1, 0, cc - 1);
}
void updBegin(int x, int k) {
// cout << "BEG " << x << " " << k << "\n";
// return;
int x1 = lower_bound(all(vx), x) - vx.begin();
segt[1].upd(0, x1 - 1, x * k, 1, 0, cc - 1);
}
void updEnd(int x, int k) {
// cout << "END " << x << " " << k << "\n";
int x1 = lower_bound(all(vx), x) - vx.begin();
segt[0].upd(x1, cc - 1, x * k, 1, 0, cc - 1);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> k >> q;
vector<E> evs;
for (int i = 0; i < n; i++) {
int x, t, a, b;
cin >> x >> t >> a >> b;
t--;
evs.push_back({a, 0, x, t});
evs.push_back({b + 1, 1, x, t});
vx.push_back(x);
}
for (int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
evs.push_back({y, 2, x, i});
vx.push_back(x);
}
sort(all(vx));
vx.erase(unique(all(vx)), vx.end());
cc = vx.size();
sort(all(evs), [](const E <, const E &rt) {
return lt.p == rt.p ? lt.t < rt.t : lt.p < rt.p;
});
for (E e : evs) {
// cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n";
if (e.t == 0) {
if (!occ[e.y].empty()) {
auto it = occ[e.y].upper_bound(e.x);
if (it == occ[e.y].begin()) {
updBegin(*occ[e.y].begin(), -1);
}
else if (it == occ[e.y].end()) {
updEnd(*occ[e.y].rbegin(), -1);
}
else {
updBetween(*prev(it), *it, -1);
}
}
auto it = occ[e.y].insert(e.x);
if (it == occ[e.y].begin())
updBegin(*it, 1);
else
updBetween(*prev(it), *it, 1);
if (next(it) == occ[e.y].end())
updEnd(*it, 1);
else
updBetween(*it, *next(it), 1);
}
else if (e.t == 1) {
auto it = occ[e.y].lower_bound(e.x);
if (it == occ[e.y].begin())
updBegin(*it, -1);
else
updBetween(*prev(it), *it, -1);
if (next(it) == occ[e.y].end())
updEnd(*it, -1);
else
updBetween(*it, *next(it), -1);
it++;
occ[e.y].erase(prev(it));
if (!occ[e.y].empty()) {
if (it == occ[e.y].begin()) {
updBegin(*occ[e.y].begin(), 1);
}
else if (it == occ[e.y].end()) {
updEnd(*occ[e.y].rbegin(), 1);
}
else {
updBetween(*prev(it), *it, 1);
}
}
}
else {
e.x = lower_bound(all(vx), e.x) - vx.begin();
ans[e.y] = que(e.x, 1, 0, cc - 1, segt[0], segt[1]);
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
return 0;
}
