/*input
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <map>
#include <set>
using namespace std;
const int MAXN = 300007, INF = 900 * 1000 * 1000;
void minimize(int &x, int y) { x = (x < y ? x : y); }
void maximize(int &x, int y) { x = (x > y ? x : y); }
struct SegmentTree
{
int N;
vector<int> A;
void init(int _N)
{
for (N = _N + 5; N & (N - 1); ++N);
A.assign(N * 2, INF);
}
void modify(int l, int r, int x)
{
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if (l & 1) minimize(A[l++], x);
if (r & 1) minimize(A[--r], x);
}
}
int get(int i)
{
int ans = INF;
for (i += N; i >= 1; i >>= 1) minimize(ans, A[i]);
return ans;
}
} it;
int N, Q, K;
struct Store { int x, t, a, b, i; } S[MAXN];
struct Border
{
int x, t, a, b, v;
Border(int _x = 0, int _t = 0, int _a = 0, int _b = 0, int _v = 0): x(_x), t(_t), a(_a), b(_b), v(_v) {}
};
struct Query
{
int x, y, i;
};
int last[MAXN * 2], ans[MAXN];
map<int, vector<int>> events;
set<pair<int, int>> curSet[MAXN];
vector<Border> rightBorder, leftBorder;
vector<Query> queries;
vector<int> times;
void addBorder(pair<int, int> p, pair<int, int> q, int t, int curTime)
{
int i = p.second, j = q.second;
int x = (p.first + q.first) >> 1;
// cout << "add " << i << ' ' << j << ' ' << x << ' ' << curTime << endl;
int a = last[i], b = curTime;
last[i] = curTime;
// if (t == 2) cout << "border " << x << ' ' << a << ' ' << b << ' ' << t << ": " << p.first << ' ' << q.first << " - " << i << endl;
if (i > N && j > N) {
leftBorder.emplace_back(-INF, t, a, b, INF);
rightBorder.emplace_back(INF, t, a, b, -INF);
} else {
leftBorder.emplace_back(x, t, a, b, q.first);
rightBorder.emplace_back(x, t, a, b, p.first);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> K >> Q;
for (int i = 1; i <= N; ++i) {
cin >> S[i].x >> S[i].t >> S[i].a >> S[i].b; S[i].i = i;
// cout << i << ": " << S[i].a << ' ' << S[i].b << endl;
S[i].x *= 2, ++S[i].b;
events[S[i].a].push_back(i);
events[S[i].b].push_back(i);
}
for (int t = 1; t <= K; ++t) {
last[N + t] = 0;
curSet[t].emplace(-INF, N + t);
curSet[t].emplace(INF, N + t);
}
for (auto ts : events) {
int curTime = ts.first;
for (int i : ts.second) {
int t = S[i].t, x = S[i].x;
if (S[i].a == curTime) {
last[i] = curTime;
curSet[t].emplace(x, i);
auto j = curSet[t].find(make_pair(x, i));
addBorder(*prev(j), *next(j), t, curTime);
} else {
auto j = curSet[t].find(make_pair(x, i));
addBorder(*prev(j), *j, t, curTime);
addBorder(*j, *next(j), t, curTime);
curSet[t].erase(j);
}
}
}
for (int t = 1; t <= K; ++t) addBorder(*curSet[t].begin(), *curSet[t].rbegin(), t, INF);
times.push_back(-INF);
for (auto &b : leftBorder) times.push_back(b.a), times.push_back(b.b);
for (auto &b : rightBorder) times.push_back(b.a), times.push_back(b.b);
sort(times.begin(), times.end());
times.erase(unique(times.begin(), times.end()), times.end());
// for (int x : times) cout << x << ' '; cout << endl;
for (auto &b : leftBorder) {
b.a = (int) (upper_bound(times.begin(), times.end(), b.a) - times.begin());
b.b = (int) (upper_bound(times.begin(), times.end(), b.b) - times.begin());
}
for (auto &b : rightBorder) {
b.a = (int) (upper_bound(times.begin(), times.end(), b.a) - times.begin());
b.b = (int) (upper_bound(times.begin(), times.end(), b.b) - times.begin());
}
queries.resize(Q);
for (int i = 0; i < Q; ++i) {
cin >> queries[i].x >> queries[i].y;
queries[i].x *= 2;
queries[i].y = (int) (upper_bound(times.begin(), times.end(), queries[i].y) - times.begin());
queries[i].i = i;
}
sort(leftBorder.begin(), leftBorder.end(), [&](Border a, Border b) { return a.x < b.x; });
sort(rightBorder.begin(), rightBorder.end(), [&](Border a, Border b) { return a.x > b.x; });
for (int i = 0; i < Q; ++i) ans[i] = -1;
sort(queries.begin(), queries.end(), [&](Query p, Query q) { return p.x > q.x; });
it.init((int) times.size());
auto b = rightBorder.begin();
for (auto &q : queries) {
for (; b != rightBorder.end() && b->x >= q.x; ++b) {
// cout << "r " << b->x << ": " << b->a << ' ' << b->b << ' ' << b->v << endl;
it.modify(b->a, b->b, b->v);
}
int x = it.get(q.y);
// cout << "g " << q.y << ": " << q.x << " - " << x << ", " << q.i << endl;
if (x != INF) maximize(ans[q.i], q.x - x);
}
// cout << "-" << endl;
reverse(queries.begin(), queries.end());
it.init((int) times.size());
b = leftBorder.begin();
for (auto &q : queries) {
for (; b != leftBorder.end() && b->x <= q.x; ++b) {
// cout << "l " << b->x << ": " << b->a << ' ' << b->b << ' ' << b->v << endl;
it.modify(b->a, b->b, -b->v);
}
int x = -it.get(q.y);
// cout << "g " << q.y << ": " << q.x << " - " << x << ", " << q.i << endl;
if (x != -INF) maximize(ans[q.i], x - q.x);
}
// cout << "-" << endl;
for (int i = 0; i < Q; ++i) {
if (ans[i] >= 200 * 1000 * 1000) ans[i] = -2;
cout << (ans[i] / 2) << '\n';
}
}
