#pragma gcc optimize("Ofast")
#pragma gcc optimize("O3")
#pragma gcc target("avx2")
#include <bits/stdc++.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(a, n) 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) { return stream << a.fi << ' ' << a.se; }
const int INF32 = 0x3f3f3f3f;
const int N = 300005;
int n, types, Q;
struct shop_t
{
int x, tp, t1, t2;
} s[N];
struct query_t
{
int x, t;
} qr[N];
int qord[N], whenq[N], 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, pair<int, pii>> ts[N];
struct ray_t
{
int x1, x2, w, tp;
bool operator < (const ray_t &oth) const
{
if (x1 != oth.x1) return x1 < oth.x1;
if (x2 != oth.x2) return x2 < oth.x2;
if (w != oth.w) return w < oth.w;
return tp < oth.tp;
}
};
struct event2_t
{
int x, tp, val;
bool operator < (const event2_t& oth) const
{
if (x != oth.x) return x < oth.x;
return tp < oth.tp;
}
};
struct event3_t
{
char tp;
int val;
};
namespace lnk
{
const int maxV = 60000007;
int V = 1;
event3_t val[maxV];
int nxt[maxV];
void add(int &i, event3_t x)
{
if (V == maxV)
{
exit(0);
}
val[V] = x;
nxt[V] = i;
i = V++;
}
}
namespace sgt
{
const int logN = 19;
const int NN = 1 << logN;
// vector<event2_t> ev[2][2 * NN];
int ev[2][2 * NN];
void add_event(event3_t e, int w, int l, int r)
{
for (l += NN, r += NN; l <= r; l >>= 1, r >>= 1)
{
if (l & 1) lnk::add(ev[w][l++], e);
if (~r & 1) lnk::add(ev[w][r--], e);
}
}
void add_query(event3_t e, int t)
{
for (t += NN; t >= 1; t >>= 1)
{
lnk::add(ev[0][t], e);
lnk::add(ev[1][t], e);
}
}
event3_t temp[12 * N];
void dfs(int v, int vl, int vr)
{
{
int mx = -INF32;
int sz = 0;
for (int idx = ev[1][v]; idx; idx = lnk::nxt[idx])
{
temp[sz++] = lnk::val[idx];
}
reverse(temp, temp + sz);
for (int i = 0; i < sz; ++i)
{
auto &e = temp[i];
if (e.tp == 0)
{
chkmax(mx, e.val);
}
else
{
int j = e.val;
auto &q = qr[j];
chkmax(ans[j], mx - q.x);
}
}
}
{
int mn = INF32;
for (int idx = ev[0][v]; idx; idx = lnk::nxt[idx])
{
auto e = lnk::val[idx];
if (e.tp == 2)
{
chkmin(mn, e.val);
}
else
{
int j = e.val;
auto &q = qr[j];
chkmax(ans[j], q.x - mn);
}
}
}
if (vl != vr)
{
int vm = (vl + vr) >> 1;
dfs(v << 1, vl, vm);
dfs(v << 1 | 1, vm + 1, vr);
}
}
}
const int MAXRAYS = 10 * N;
ray_t rays[MAXRAYS];
int rays_t1[MAXRAYS];
int rays_cnt;
pair<event2_t, pii> ep[2 * MAXRAYS];
int ep_sz;
signed main()
{
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> types >> Q;
for (int i = 0; i < n; ++i)
{
auto &e = s[i];
cin >> e.x >> e.tp >> e.t1 >> e.t2;
--e.tp;
ev[events++] = {e.t1, 0, i};
ev[events++] = {e.t2, 2, i};
}
for (int j = 0; j < Q; ++j)
{
auto &q = qr[j];
cin >> q.x >> q.t;
ev[events++] = {q.t, 1, j};
}
sort(ev, ev + events);
int T = 0;
auto add_ray_ev = [&](ray_t ray, int t1, int t2)
{
if (t1 <= t2)
{
if (ray.w == 0)
{
ep[ep_sz++] = {{ray.x2, 2, ray.x1}, {t1, t2}};
}
else
{
ep[ep_sz++] = {{ray.x1, 0, ray.x2}, {t1, t2}};
}
}
};
auto add = [&](int x1, int x2, int w, int ri, int tp)
{
ray_t ray = {x1, x2, w, tp};
rays[ri] = ray;
rays_t1[ri] = T;
};
auto add2 = [&](int x1, int x2, int r0, int r1, int tp)
{
// cerr << "add2 " << x1 << ' ' << x2 << ' ' << r0 << ' ' << r1 << endl;
int xm = (x1 + x2) / 2;
add(x1, xm, 0, r0, tp);
add(xm + 1, x2, 1, r1, tp);
};
auto rem = [&](int ri)
{
// cerr << "rem " << ri << endl;
add_ray_ev(rays[ri], rays_t1[ri], T - 1);
rays_t1[ri] = -1;
};
rays_cnt = 0;
for (int tp = 0; tp < types; ++tp)
{
ts[tp].insert({-INF32, {1, {-1, rays_cnt}}});
ts[tp].insert({INF32, {1, {rays_cnt + 1, -1}}});
add2(-INF32, INF32, rays_cnt, rays_cnt + 1, tp);
rays_cnt += 2;
}
for (int ei = 0; ei < events; ++ei)
{
auto& e = ev[ei];
if (e.tp == 0)
{
int i = e.idx;
auto &f = s[i];
auto &S = ts[f.tp];
if (S.find(f.x) != S.end())
++S[f.x].fi;
else
{
S.insert({f.x, {1, {rays_cnt + 1, rays_cnt + 2}}});
auto Y = S.find(f.x);
auto Z = next(Y);
auto X = prev(Y);
rem(X->se.se.se);
rem(Z->se.se.fi);
X->se.se.se = rays_cnt;
Z->se.se.fi = rays_cnt + 3;
add2(X->fi, Y->fi, rays_cnt, rays_cnt + 1, f.tp);
add2(Y->fi, Z->fi, rays_cnt + 2, rays_cnt + 3, f.tp);
rays_cnt += 4;
assert(rays_cnt < MAXRAYS);
}
}
else if (e.tp == 2)
{
int i = e.idx;
auto &f = s[i];
auto &S = ts[f.tp];
if (--S[f.x].fi == 0)
{
auto Y = S.find(f.x);
auto Z = next(Y);
auto X = prev(Y);
rem(X->se.se.se);
rem(Y->se.se.fi);
rem(Y->se.se.se);
rem(Z->se.se.fi);
add2(X->fi, Z->fi, rays_cnt, rays_cnt + 1, f.tp);
X->se.se.se = rays_cnt;
Z->se.se.fi = rays_cnt + 1;
rays_cnt += 2;
assert(rays_cnt < MAXRAYS);
S.erase(Y);
}
}
else
{
qord[T] = e.idx;
whenq[e.idx] = T;
++T;
}
}
for (int ri = 0; ri < rays_cnt; ++ri)
{
if (rays_t1[ri] == -1) continue;
add_ray_ev(rays[ri], rays_t1[ri], T - 1);
}
for (int j = 0; j < Q; ++j)
{
auto &q = qr[j];
ep[ep_sz++] = {{q.x, 1, j}, {whenq[j], -1}};
}
sort(ep, ep + ep_sz);
debug(clock() * 1.0 / CLOCKS_PER_SEC);
for (int ep_i = 0; ep_i < ep_sz; ++ep_i)
{
auto &el = ep[ep_i];
auto &e = el.fi;
int t1 = el.se.fi;
int t2 = el.se.se;
if (t2 != -1)
{
sgt::add_event({e.tp, e.val}, e.tp == 2 ? 0 : 1, t1, t2);
}
else
{
sgt::add_query({e.tp, e.val}, t1);
}
}
debug(clock() * 1.0 / CLOCKS_PER_SEC);
fill(ans, ans + Q, -INF32);
sgt::dfs(1, 0, sgt::NN - 1);
for (int j = 0; j < Q; ++j)
cout << (ans[j] >= INF32 / 2 ? -1 : ans[j]) << '\n';
debug(clock() * 1.0 / CLOCKS_PER_SEC);
return 0;
}
