#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc target("avx2")
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <fstream>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <random>
#include <time.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(...) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &a) { for (auto& x : a) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2> &a) { stream << a.fi << ' ' << a.se; return stream; }
const int INF32 = 0x3f3f3f3f;
const int N = 3e5 + 5;
bool task3, task34;
int rx[2 * N], X;
int n, Q, types;
struct shop_t
{
int x, tp, t1, t2;
} s[N];
struct query_t
{
int x, t, idx;
} qr[N];
int ans[N];
struct event_t
{
int t, tp, idx;
bool operator < (const event_t& oth) const
{
if (t != oth.t)
return t < oth.t;
return tp < oth.tp;
}
} ev[3 * N];
int events;
map<int, int> type_on[N];
int tp_cnt[N];
namespace treap
{
mt19937 rng(time(0));
struct Node
{
int x, y;
Node *l, *r;
Node() {}
Node(int _x): x(_x), y(rng()), l(0), r(0) {}
};
Node* merge(Node* a, Node* b)
{
if (!a) return b;
if (!b) return a;
if (a->y > b->y)
{
a->r = merge(a->r, b);
return a;
}
else
{
b->l = merge(a, b->l);
return b;
}
}
pair<Node*, Node*> split(Node *t, int x)
{
if (!t) return {0, 0};
if (t->x < x)
{
auto p = split(t->r, x);
t->r = p.fi;
return {t, p.se};
}
else
{
auto p = split(t->l, x);
t->l = p.se;
return {p.fi, t};
}
}
void add(Node *&t, int x)
{
auto p = split(t, x);
t = merge(p.fi, merge(new Node(x), p.se));
}
void rem(Node *&t, int x)
{
if (!t) return;
if (t->x == x)
{
t = merge(t->l, t->r);
}
else if (t->x < x)
{
rem(t->r, x);
}
else
{
rem(t->l, x);
}
}
int gmin(Node *t)
{
if (!t) return INF32;
for (; t->l; t = t->l);
return t->x;
}
int gmax(Node *t)
{
if (!t) return INF32;
for (; t->r; t = t->r);
return t->x;
}
}
namespace sgt
{
const int logN = 20;
const int N = 1 << logN;
treap::Node* S[2 * N];
int min3[2 * N], max3[2 * N];
void init()
{
memset(S, 0, sizeof S);
memset(min3, 0x3f, sizeof min3);
for (int i = 0; i < 2 * N; ++i)
max3[i] = -INF32;
}
void mdf(int v, int vl, int vr, int l, int r, int x, bool rem = false)
{
if (l > r || vr < l || r < vl) return;
if (l <= vl && vr <= r)
{
if (!rem)
{
if (!task34)
{
treap::add(S[v], x);
}
else
{
chkmin(min3[v], x);
chkmax(max3[v], x);
}
}
else
{
if (!task34)
treap::rem(S[v], x);
}
return;
}
int vm = (vl + vr) >> 1;
mdf(v << 1, vl, vm, l, r, x, rem);
mdf(v << 1 | 1, vm + 1, vr, l, r, x, rem);
}
pii gt(int pos)
{
int min_x = INF32, max_x = -INF32;
int v = 1, vl = 0, vr = X - 1;
while (true)
{
if (!task34)
{
if (S[v])
{
chkmin(min_x, treap::gmin(S[v]));
chkmax(max_x, treap::gmax(S[v]));
}
}
else
{
chkmin(min_x, min3[v]);
chkmax(max_x, max3[v]);
}
if (vl == vr) break;
int vm = (vl + vr) >> 1;
if (pos <= vm)
{
v <<= 1;
vr = vm;
}
else
{
v <<= 1;
++v;
vl = vm + 1;
}
}
return {min_x, max_x};
}
}
signed main()
{
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
sgt::init();
cin >> n >> types >> Q;
task3 = task34 = true;
for (int i = 0; i < n; ++i)
{
cin >> s[i].x >> s[i].tp >> s[i].t1 >> s[i].t2;
task34 &= s[i].t1 == 1;
task3 &= s[i].t2 == 100000000;
--s[i].tp;
rx[X++] = s[i].x;
ev[events++] = {s[i].t1, 0, i};
ev[events++] = {s[i].t2, 2, i};
}
task3 &= task34;
for (int j = 0; j < Q; ++j)
{
cin >> qr[j].x >> qr[j].t;
qr[j].idx = j;
rx[X++] = qr[j].x;
ev[events++] = {qr[j].t, 1, j};
}
sort(rx, rx + X);
X = unique(rx, rx + X) - rx;
// for (int x = 0; x < X; ++x)
// cx[rx[x]] = x;
auto mdf = [&](int xl, int xr, int val, bool rem)
{
if (val == -INF32 || val == INF32) return;
int il = lower_bound(rx, rx + X, xl) - rx;
int ir = upper_bound(rx, rx + X, xr) - rx - 1;
if (il > ir) return;
sgt::mdf(1, 0, X - 1, il, ir, val, rem);
};
auto mdf2 = [&](int x1, int x2, bool rem)
{
int xm = (x1 + x2) / 2;
mdf(x1, xm, x1, rem);
mdf(xm + 1, x2, x2, rem);
};
for (int tp = 0; tp < types; ++tp)
{
type_on[tp].insert({INF32, 1});
type_on[tp].insert({-INF32, 1});
}
if (task34)
{
for (int i = 0; i < n; ++i)
{
auto &a = s[i];
if (!type_on[a.tp].count(a.x))
type_on[a.tp].insert({a.x, 1});
else
++type_on[a.tp][a.x];
}
for (int tp = 0; tp < types; ++tp)
{
auto &S = type_on[tp];
auto x = S.begin();
auto y = next(x);
while (y != S.end())
{
mdf2(x->fi, y->fi, false);
x = y;
y = next(y);
}
}
}
sort(ev, ev + events);
int active_tp = 0;
for (int ei = 0; ei < events; ++ei)
{
auto &e = ev[ei];
if (e.tp == 0)
{
int i = e.idx;
auto &a = s[i];
if (++tp_cnt[a.tp] == 1)
++active_tp;
if (task34) continue;
auto &S = type_on[a.tp];
if (S.find(a.x) != S.end())
++S[a.x];
else
{
S.insert({a.x, 1});
auto it = S.find(a.x);
int x1 = prev(it)->fi;
int x2 = next(it)->fi;
mdf2(x1, x2, true);
mdf2(x1, a.x, false);
mdf2(a.x, x2, false);
}
}
else if (e.tp == 2)
{
if (task34 && task3) break;
int i = e.idx;
auto &a = s[i];
if (--tp_cnt[a.tp] == 0)
--active_tp;
auto &S = type_on[a.tp];
if (--S[a.x] == 0)
{
auto it = S.find(a.x);
int x1 = prev(it)->fi;
int x2 = next(it)->fi;
S.erase(it);
mdf2(x1, a.x, true);
mdf2(a.x, x2, true);
mdf2(x1, x2, false);
}
}
else
{
int j = e.idx;
auto &q = qr[j];
if (active_tp < types)
ans[j] = INF32;
else
{
auto res = sgt::gt(lower_bound(rx, rx + X, q.x) - rx);
ans[j] = max(labs(q.x - res.fi), labs(q.x - res.se));
}
}
}
for (int j = 0; j < Q; ++j)
cout << (ans[j] >= INF32 ? -1 : ans[j]) << '\n';
return 0;
}
