#include <bits/stdc++.h>
using namespace std;
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
template<class T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; }
template<class T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; }
template<class T> int lwb(vector<T> &a, T& b) { return lower_bound(all(a), b) - a.begin(); }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }
const int N = 3e5 + 5;
const int INF = 1e9;
struct event {
int type, x, time, id;
event(int type = 0, int x = 0, int time = 0, int id = 0) : type(type), x(x), time(time), id(id) {}
};
vector<event> events;
vector<int> compress;
multiset<int> save[N];
multiset<int> nxt_pos[N];
int ans[N];
struct IT {
vector<ll> st;
int n;
IT(int n) : n(n), st(4 * n + 5) {}
void update(int id, int l, int r, int pos, ll val) {
if (l > pos || r < pos)
return;
if (l == r) {
st[id] = val;
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, pos, val);
update(id << 1 | 1, mid + 1, r, pos, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
ll get(int id, int l, int r, int u, int v) {
if (l > v || r < u)
return -INF;
if (u <= l && r <= v)
return st[id];
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
void update(int pos) {
ll val = 0;
if (!nxt_pos[pos].empty()) val = *(nxt_pos[pos].rbegin());
update(1, 1, n, pos, val);
}
ll query(int l, int r) {
if (l > r) return -INF;
return get(1, 1, n, l, r);
}
};
int n, k, q;
void solve() {
cin >> n >> k >> q;
FOR(i, 1, n) {
int x, t, l, r;
cin >> x >> t >> l >> r;
events.eb(0, x, l, t);
events.eb(1, x, r + 1, t);
compress.eb(x);
}
FOR(i, 1, q) {
int x, t;
cin >> x >> t;
events.eb(2, x, t, i);
}
compress.eb(-INF);
compress.eb(INF);
sort(all(compress));
compact(compress);
sort(all(events), [&](event u, event v) {
if (u.time == v.time) return u.type < v.type;
else return u.time < v.time;
});
FOR(i, 1, k) {
save[i].insert(-INF); save[i].insert(INF);
nxt_pos[1].insert(INF);
}
IT st(sz(compress));
st.update(1);
auto add = [&](int l, int r) -> void {
l = lwb(compress, l) + 1;
nxt_pos[l].insert(r);
st.update(l);
};
auto del = [&](int l, int r) -> void {
l = lwb(compress, l) + 1;
nxt_pos[l].erase(nxt_pos[l].find(r));
st.update(l);
};
auto update = [&](int type, int x, int id) -> void {
// cerr << (type == 0 ? "add" : "del") << el;
if (type == 0) { // add
save[id].insert(x);
int prv = -INF;
int nxt = INF;
auto it = save[id].lower_bound(x);
if (next(it) != save[id].end()) nxt = *(next(it));
if (it != save[id].begin()) prv = *(prev(it));
// cerr << prv << " " << nxt << el;
del(prv, nxt);
add(prv, x);
add(x, nxt);
}
else { // del
int prv = -INF;
int nxt = INF;
auto it = save[id].lower_bound(x);
if (next(it) != save[id].end()) nxt = *(next(it));
if (it != save[id].begin()) prv = *(prev(it));
save[id].erase(it);
// cerr << prv << " " << nxt << el;
del(prv, x);
// cerr << "ok" << el;
del(x, nxt);
add(prv, nxt);
}
};
auto query = [&](int x) -> int {
int l = 0;
int r = 1e8;
int ans = -1;
while(l <= r) {
int mid = (l + r) >> 1;
int bound_left = max(1, x - mid);
int bound_right = min(100000000, x + mid);
bound_left = lwb(compress, bound_left) + 1;
if (st.query(1, bound_left - 1) <= bound_right) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
return ans;
};
for(auto [type, x, time, id] : events) {
// cerr << type << ": " << x << " " << id << el;
if (type != 2) {
update(type, x, id);
}
else {
ans[id] = query(x);
}
}
FOR(i, 1, q) cout << ans[i] << el;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#define task "task"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
solve();
return 0;
}
/*
*/
