#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
struct store {
int pos, type, left_T, right_T;
};
struct query {
int pos, T;
};
const int inf = 1e8 + 20;
const int maxn = 3e5 + 20;
int tr[maxn * 4];
store S[maxn];
query Q[maxn];
set<int> bad[maxn];
set<int> val_pos[maxn];
int res[maxn];
int n, k, q;
void update(int id, int lt, int rt, int pos, int val) {
if (lt == rt) {
tr[id] = val;
return;
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
update(id * 2, lt, mt, pos, val);
}
else {
update(id * 2 + 1, mt + 1, rt, pos, val);
}
tr[id] = max(tr[id * 2], tr[id * 2 + 1]);
}
int get(int id, int lt, int rt, int pos) {
if (lt == rt) {
return tr[id];
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
return get(id * 2, lt, mt, pos);
}
else {
return max(tr[id * 2], get(id * 2 + 1, mt + 1, rt, pos));
}
}
void add_bad(int lt, int rt, int val) {
if (lt > rt) {
return;
}
if (rt == n) {
rt += val - 1;
}
bad[lt].insert(rt);
update(1, 1, n, lt, (bad[lt].empty() ? -inf : *bad[lt].rbegin()));
}
void rem_bad(int lt, int rt, int val) {
if (lt > rt) {
return;
}
if (rt == n) {
rt += val - 1;
}
bad[lt].erase(rt);
update(1, 1, n, lt, (bad[lt].empty() ? -inf : *bad[lt].rbegin()));
}
void add_val(int pos, int val) {
auto it = val_pos[val].insert(pos).first;
int prv = (it == val_pos[val].begin() ? 0 : *prev(it));
int nxt = (next(it) == val_pos[val].end() ? n + 1 : *next(it));
rem_bad(prv + 1, nxt - 1, val);
add_bad(prv + 1, pos - 1, val);
add_bad(pos + 1, nxt - 1, val);
}
void rem_val(int pos, int val) {
auto it = val_pos[val].lower_bound(pos);
int prv = (it == val_pos[val].begin() ? 0 : *prev(it));
int nxt = (next(it) == val_pos[val].end() ? n + 1 : *next(it));
rem_bad(prv + 1, pos - 1, val);
rem_bad(pos + 1, nxt - 1, val);
add_bad(prv + 1, nxt - 1, val);
val_pos[val].erase(it);
}
bool check(int lt, int rt) {
if (lt > rt) {
return false;
}
return get(1, 1, n, lt) < rt;
}
void just_do_it() {
fill_n(tr, maxn * 4, -inf);
cin >> n >> k >> q;
for (int i = 1; i <= k; i++) {
add_bad(1, n, i);
}
vector<pair<int, int>> sorted_pos;
vector<pair<int, pair<int, int>>> events;
for (int i = 1; i <= n; i++) {
cin >> S[i].pos >> S[i].type >> S[i].left_T >> S[i].right_T;
sorted_pos.push_back({S[i].pos, i});
events.push_back({S[i].left_T, {1, i}});
events.push_back({S[i].right_T, {3, i}});
}
sort(sorted_pos.begin(), sorted_pos.end());
for (int i = 1; i <= n; i++) {
S[sorted_pos[i - 1].second].pos = i;
}
for (int i = 1; i <= q; i++) {
cin >> Q[i].pos >> Q[i].T;
events.push_back({Q[i].T, {2, i}});
}
sort(events.begin(), events.end());
for (auto e: events) {
int type = e.second.first;
int id = e.second.second;
if (type == 1) {
add_val(S[id].pos, S[id].type);
}
if (type == 2) {
res[id] = -1;
int lt = 0;
int rt = inf;
while (lt <= rt) {
int mt = (lt + rt) / 2;
int ql = lower_bound(sorted_pos.begin(), sorted_pos.end(), make_pair(Q[id].pos - mt, -inf)) - sorted_pos.begin() + 1;
int qr = upper_bound(sorted_pos.begin(), sorted_pos.end(), make_pair(Q[id].pos + mt, inf)) - sorted_pos.begin();
if (check(ql, qr)) {
res[id] = mt;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
}
if (type == 3) {
rem_val(S[id].pos, S[id].type);
}
}
for (int i = 1; i <= q; i++) {
cout << res[i] << '\n';
}
}
