#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; i++)
#define f0r(i, a) f1r(i, 0, a)
#define trav(t, a) for (auto& t : a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
const int N = 3e5 + 1;
const int M = (1 << 21);
const int INF = 1e9;
template <class T> bool ckmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
int get_pos(vi& v, int x) { return upper_bound(all(v), x) - v.begin(); }
template <int N> struct SegmentTree {
vector<array<int, 4>> todo;
// loc to loc, time to time
vi num;
int mn[N];
void build(int ind, int L, int R) {
mn[ind] = 2 * INF;
if (L == R) return;
int M = (L + R) >> 1;
build(2*ind, L, M);
build(2*ind+1, M+1, R);
}
void build() {
num.pb(-INF);
trav(a, todo) num.pb(a[2]), num.pb(a[3]+1);
sort(all(num));
num.erase(unique(all(num)), num.end());
build(1, 0, sz(num)-1);
}
void modify(int x, int y, int t, int ind, int L, int R) {
if (R < x || y < L) return;
if (x <= L && R <= y) {
ckmin(mn[ind], t);
return;
}
int M = (L + R) >> 1;
modify(x, y, t, 2*ind, L, M);
modify(x, y, t, 2*ind+1, M+1, R);
}
void modify(int x, int y, int t) {
modify(get_pos(num, x), get_pos(num, y), t, 1, 0, sz(num)-1);
}
int query(int x, int ind, int L, int R) {
int ret = mn[ind];
if (L != R) {
int M = (L + R) >> 1;
if (x <= M) {
ckmin(ret, query(x, 2*ind, L, M));
} else {
ckmin(ret, query(x, 2*ind+1, M+1, R));
}
}
return ret;
}
int query(int x) {
return query(get_pos(num, x), 1, 0, sz(num)-1);
}
};
int n, k, q;
int ans[N]; // stores answers
map<pi, int> type[N];
vector<array<int, 5>> mod; // modifications
vector<array<int, 3>> query; // queries
SegmentTree<M> S[2];
void insert(int x, pair<pi, int> a, pair<pi, int> b) {
if (a.f.f == -INF && b.f.f == INF) {
S[0].todo.pb({INF, -INF, a.s, x});
S[1].todo.pb({-INF, INF, a.s, x});
} else {
int m = (a.f.f+b.f.f) >> 1;
S[0].todo.pb({m, a.f.f, a.s, x});
S[1].todo.pb({m+1, b.f.f, a.s, x});
}
}
pair<pi, int> get_next(map<pi, int>& a, map<pi, int>::iterator b) {
b = next(b);
if (b == a.end()) return {{INF, -1}, 1};
else return *b;
}
void init() {
cin.tie(0)->sync_with_stdio();
cin >> n >> k >> q;
f0r(i, n) {
int x, t, a, b; cin >> x >> t >> a >> b;
mod.push_back({a, 1, t, x, i});
mod.push_back({b+1, -1, t, x, i});
}
f1r(i, 1, k+1) {
type[i][{-INF, -1}] = 1;
}
sort(all(mod));
trav(a, mod) {
pi t = {a[3], a[4]};
if (a[1] == 1) { // adding something
type[a[2]][t] = 0;
auto it = type[a[2]].find(t);
insert(a[0]-1, *prev(it), get_next(type[a[2]], it)); // adds the things that ended
prev(it)->s = it->s = a[0]; // this is when they started a new thing
} else { // removing something
auto it = type[a[2]].find(t);
insert(a[0]-1, *prev(it), *it);
insert(a[0]-1, *it, get_next(type[a[2]], it));
prev(it)->s = a[0]; // set previous time
type[a[2]].erase(it); // get rid of thing
}
}
f1r(i, 1, k+1) {
insert(1e8, *type[i].begin(), get_next(type[i], type[i].begin())); // set the remainder that didn't get removed, which is the negative infinity
// this is so we don't ever have nothing?
// figure this out
}
f0r(i, q) {
int l, y; cin >> l >> y;
query.pb({l, y, i});
}
}
void solve0() {
sort(query.rbegin(), query.rend());
S[0].build();
sort(all(S[0].todo));
trav(a, query) {
while (sz(S[0].todo)) {
auto x = S[0].todo.back();
if (x[0] < a[0]) break; // doesn't affect
S[0].modify(x[2], x[3], x[1]);
S[0].todo.pop_back();
}
ckmax(ans[a[2]], a[0]-S[0].query(a[1]));
}
}
void solve1() {
reverse(all(query));
S[1].build();
sort(S[1].todo.rbegin(), S[1].todo.rend());
trav(a, query) {
while (sz(S[1].todo)) {
auto x = S[1].todo.back();
if (x[0] > a[0]) break; // doesn't apply
S[1].modify(x[2], x[3], -x[1]);
S[1].todo.pop_back();
}
ckmax(ans[a[2]], -S[1].query(a[1])-a[0]);
}
}
int main() {
init();
solve0();
solve1();
f0r(i, q) {
if (ans[i] > 1e8) cout << -1;
else cout << ans[i];
cout << '\n';
}
return 0;
}
