#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
const int SIZE = 1 << 20;
struct ST {
int A[2 * SIZE];
void init() { fill(A, A + 2 * SIZE, -1e9); }
void update(int x, int v) {
x += SIZE; A[x] = v;
for (x >>= 1; x; x >>= 1) A[x] = max(A[x << 1], A[x << 1 | 1]);
}
int query(int s, int e) {
int ret = -1e9;
for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
if ( s & 1) ret = max(ret, A[s++]);
if (~e & 1) ret = max(ret, A[e--]);
}
return ret;
}
} seg;
int N, K, Q;
vector<pair<int, pii> > qin, qout, qry;
vector<pii> xx;
int ans[300005];
multiset<int> MS[300005];
void solve() {
sort(qin.begin(), qin.end());
sort(qout.begin(), qout.end());
sort(qry.begin(), qry.end());
xx.clear();
seg.init();
int j = 0, k = 0;
for (auto i : qry) {
while (j < qin.size() && qin[j].ff <= i.ff) {
int x = qin[j].ss.ff, c = qin[j].ss.ss;
auto it = MS[c].lower_bound(x);
xx.emplace_back((*it + x) / 2, c);
--it;
xx.emplace_back((x + *it) / 2, c);
MS[c].insert(x);
++j;
}
while (k < qout.size() && qout[k].ff < i.ff) {
int x = qout[k].ss.ff, c = qout[k].ss.ss;
MS[c].erase(MS[c].find(x));
++k;
}
}
while (j < qin.size()) {
int x = qin[j].ss.ff, c = qin[j].ss.ss;
MS[c].insert(x);
++j;
}
while (k < qout.size()) {
int x = qout[k].ss.ff, c = qout[k].ss.ss;
MS[c].erase(MS[c].find(x));
++k;
}
sort(xx.begin(), xx.end());
j = k = 0;
int cnt = 0;
for (auto i : qry) {
while (j < qin.size() && qin[j].ff <= i.ff) {
int x = qin[j].ss.ff, c = qin[j].ss.ss, t, p, q;
auto it = MS[c].lower_bound(x);
if (MS[c].size() == 2) ++cnt;
if (*it != x) {
auto jt = it;
--jt;
t = lower_bound(xx.begin(), xx.end(), pii((*it + *jt) / 2, c)) - xx.begin();
p = lower_bound(xx.begin(), xx.end(), pii((*it + x) / 2, c)) - xx.begin();
q = lower_bound(xx.begin(), xx.end(), pii((x + *jt) / 2, c)) - xx.begin();
if (MS[c].size() > 2) seg.update(t, -1e9);
seg.update(p, *it);
seg.update(q, x);
}
MS[c].insert(x);
++j;
}
while (k < qout.size() && qout[k].ff < i.ff) {
int x = qout[k].ss.ff, c = qout[k].ss.ss, t, p, q;
MS[c].erase(MS[c].find(x));
++k;
auto it = MS[c].lower_bound(x);
if (*it != x) {
auto jt = it;
--jt;
t = lower_bound(xx.begin(), xx.end(), pii((*it + *jt) / 2, c)) - xx.begin();
p = lower_bound(xx.begin(), xx.end(), pii((*it + x) / 2, c)) - xx.begin();
q = lower_bound(xx.begin(), xx.end(), pii((x + *jt) / 2, c)) - xx.begin();
if (MS[c].size() > 2) seg.update(t, *it);
seg.update(p, -1e9);
seg.update(q, -1e9);
}
if (MS[c].size() == 2) --cnt;
}
if (cnt == K) ans[i.ss.ss] = max(ans[i.ss.ss], (seg.query(0, lower_bound(xx.begin(), xx.end(), pii(i.ss.ff + 1, 0)) - xx.begin() - 1) - i.ss.ff) / 2);
}
while (j < qin.size()) {
int x = qin[j].ss.ff, c = qin[j].ss.ss;
MS[c].insert(x);
++j;
}
while (k < qout.size()) {
int x = qout[k].ss.ff, c = qout[k].ss.ss;
MS[c].erase(MS[c].find(x));
++k;
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> K >> Q;
fill(ans, ans + Q, -1);
for (int i = 1; i <= K; ++i) {
MS[i].insert(1e9);
MS[i].insert(-1e9);
}
for (int i = 0; i < N; ++i) {
int a, b, c, d; cin >> a >> b >> c >> d;
a *= 2;
qin.emplace_back(c, pii(a, b));
qout.emplace_back(d, pii(a, b));
}
for (int i = 0; i < Q; ++i) {
int a, b; cin >> a >> b;
a *= 2;
qry.emplace_back(b, pii(a, i));
}
solve();
for (auto &i : qin) i.ss.ff = -i.ss.ff;
for (auto &i : qout) i.ss.ff = -i.ss.ff;
for (auto &i : qry) i.ss.ff = -i.ss.ff;
solve();
for (int i = 0; i < Q; ++i) printf("%d\n", ans[i]);
return 0;
}
