#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#define int ll
#define pii pll
enum EventType {Rem, Add, Query};
struct Event {
int time;
EventType type;
int store;
int pos;
int query_idx;
};
bool operator<(const Event &a, const Event &b) {
return a.time < b.time || a.time == b.time && a.type < b.type;
}
vector<Event> evs;
vector<set<pii>> type_list;
struct Seg {
int *t;
int begin, end;
void init(int b, int e) {
t = new int[4 * (e-b)];
fill(t, t + 4*(e-b), INT_MIN);
begin = b;
end = e;
}
void up_impl(int p, int x, int i, int b, int e) {
if (e-b==1) {
t[i] = x;
return;
}
if (p < (b+e)/2)
up_impl(p, x, 2*i+1, b, (b+e)/2);
else
up_impl(p, x, 2*i+2, (b+e)/2, e);
t[i] = max(t[2*i+1], t[2*i+2]);
}
int get_impl(int l, int r, int i, int b, int e) {
if (l <= b && e <= r)
return t[i];
if (r <= b || e <= l)
return INT_MIN;
return max(get_impl(l, r, 2*i+1, b, (b+e)/2),
get_impl(l, r, 2*i+2, (b+e)/2, e));
}
void up(int p, int x) { return up_impl(p, x, 0, begin, end); }
int get(int l, int r) { return get_impl(l, r, 0, begin, end); }
} next_right;
int cnt_types, cnt_stores, cnt_queries;
vector<int> store_poses;
struct Store {
int type;
int pos;
int b, e;
};
bool operator<(const Store &a, const Store &b) { return a.pos < b.pos; }
vector<Store> stores;
vector<int> ans;
void handle_add(Event ev)
{
Store s = stores[ev.store];
auto &list = type_list[s.type];
auto it = list.upper_bound({s.pos, ev.store});
int p = it == list.end()? INT_MAX: it->first;
--it;
next_right.up(it->second, s.pos);
next_right.up(ev.store, p);
list.insert({s.pos, ev.store});
}
void handle_rem(Event ev)
{
Store s = stores[ev.store];
auto &list = type_list[s.type];
auto it = list.upper_bound({s.pos, ev.store});
int p = it == list.end()? INT_MAX: it->first;
--it; --it;
next_right.up(it->second, p);
next_right.up(ev.store, INT_MIN);
list.erase({s.pos, ev.store});
}
void handle_query(Event ev)
{
if (next_right.get(-cnt_types, 0) == INT_MAX) {
ans[ev.query_idx] = -1;
return;
}
int l = 0, r = INT_MAX;
auto get = [&](int e) {
e = lower_bound(store_poses.begin(), store_poses.end(), e) - store_poses.begin();
return next_right.get(-cnt_stores, e);
};
while (l < r) {
int m = (l + r)/2;
int b = ev.pos - m, e = ev.pos + m + 1;
if (get(b) < e)
r = m;
else
l = m+1;
}
ans[ev.query_idx] = l;
}
signed main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> cnt_stores >> cnt_types >> cnt_queries;
Loop (i,0,cnt_stores) {
Store s;
cin >> s.pos >> s.type >> s.b >> s.e;
--s.pos; --s.b;
stores.push_back(s);
store_poses.push_back(s.pos);
}
sort(stores.begin(), stores.end());
sort(store_poses.begin(), store_poses.end());
Loop (i,0,cnt_stores) {
evs.push_back({
.time = stores[i].b,
.type = Add,
.store = i,
.pos = stores[i].pos,
.query_idx = -1,
});
evs.push_back({
.time = stores[i].e,
.type = Rem,
.store = i,
.pos = stores[i].pos,
.query_idx = -1,
});
}
Loop (i,0,cnt_queries) {
int l, y;
cin >> l >> y;
--l; --y;
evs.push_back({
.time = y,
.type = Query,
.store = -1,
.pos = l,
.query_idx = i,
});
}
sort(evs.begin(), evs.end());
ans.resize(cnt_queries);
type_list.resize(cnt_types+1);
next_right.init(-cnt_types, cnt_stores);
Loop (i,-cnt_types,0) {
type_list[-i].insert({i, i});
next_right.up(i, INT_MAX);
}
for (Event ev : evs) {
switch (ev.type) {
case Add: handle_add(ev); break;
case Rem: handle_rem(ev); break;
case Query: handle_query(ev); break;
}
}
Loop (i,0,cnt_queries)
cout << ans[i] << '\n';
}
