#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int N = 1 << 20;
map<int,int> mp[N];
multiset<int> fe[N];
int t[N * 2];
int L, R;
inline void upd(int v, int vl, int vr, int pos, int type, int prev) {
if (vl == vr) {
if (mp[vl].find(type) == mp[vl].end()) {
mp[vl][type] = prev;
fe[vl].insert(prev);
}
else {
fe[vl].erase(fe[vl].find(mp[vl][type]));
mp[vl][type] = prev;
fe[vl].insert(prev);
}
t[v] = *fe[vl].begin();
return;
}
int m = vl + vr >> 1;
if (pos <= m) upd(2 * v + 1, vl, m, pos, type, prev);
else upd(2 * v + 2, m + 1,vr, pos, type, prev);
t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
inline void erase(int v, int vl, int vr, int pos, int type) {
if (vl == vr) {
fe[vl].erase(fe[vl].find(mp[vl][type]));
mp[vl].erase(type);
if (sz(fe[vl])) t[v] = *fe[vl].begin();
else t[v] = iinf;
return;
}
int m = vl + vr >> 1;
if (pos <= m) erase(2 * v + 1, vl, m, pos, type);
else erase(2 * v + 2, m + 1, vr, pos, type);
t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
inline int get(int v, int vl, int vr, int l, int r) {
if (vl == l && vr == r) return t[v];
int m = vl + vr >> 1;
if (r <= m) return get(2 * v + 1, vl, m, l, r);
else if (l > m) return get(2 * v + 2, m + 1, vr, l, r);
else return min(get(2 * v + 1, vl, m, l, m), get(2 * v + 2, m + 1, vr, m + 1, r));
}
inline int get(int l, int r) { if(l>r){return iinf;}return get(0, L, R, l, r); }
inline void upd(int pos, int type, int prev) { upd(0, L, R, pos, type, prev); }
inline void erase(int pos, int type) { erase(0, L, R, pos, type); }
const int M = 3e5 + 10;
ve<int> alt, al;
array<int,4> a[M];
array<int,2> f[M];
ve<pii> add[3 * M], del[3 * M], ask[3 * M];
map<int,int> g[M];
int res[M];
inline void solve() {
fill(t, t + 2 * N, iinf); al.pb(-iinf);
int n, k, q;
cin >> n >> k >> q;
for (int i = 0; i < n; ++i) {
int x, t, l, r;
cin >> x >> t >> l >> r;
a[i] = {x, t, l, r};
alt.pb(l);
alt.pb(r + 1);
al.pb(x);
}
for (int i = 0; i < q; ++i) {
int x, t;
cin >> x >> t;
alt.pb(t);
al.pb(x);
f[i] = {x, t};
}
sort(all(alt));
alt.erase(unique(all(alt)), alt.end());
sort(all(al)); al.pb(iinf);
al.erase(unique(all(al)), al.end());
L = 0, R = sz(al) - 1;
for (auto &[x, t, l, r] : a) {
l = lower_bound(all(alt), l) - alt.begin();
r = lower_bound(all(alt), r + 1) - alt.begin();
x = lower_bound(all(al), x) - al.begin();
}
for (auto &[x, t] : f) {
t = lower_bound(all(alt), t) - alt.begin();
x = lower_bound(all(al), x) - al.begin();
}
int m = sz(alt);
for (auto &[x, t, l, r] : a) {
add[l].pb({x, t});
del[r].pb({x, t});
}
for (int i = 0; i < q; ++i) {
auto &[x, t] = f[i];
ask[t].pb({x, i});
}
for (int type = 1; type <= k; ++type) add[0].pb({R, type});
for (int curt = 0; curt < m; ++curt) {
for (auto &[x, type] : add[curt]) {
auto it = g[type].upper_bound(x);
if (it != g[type].end()) upd(it->fi, type, x);
it = g[type].lower_bound(x);
if (it != g[type].begin()) {
--it;
upd(x, type, it->fi);
}
else upd(x, type, L);
++g[type][x];
}
for (auto &[x, type] : del[curt]) {
--g[type][x];
if (!g[type][x]) g[type].erase(x);
auto it = g[type].lower_bound(x);
int prev = L;
if (it != g[type].begin()) {
--it;
prev = it->fi;
}
it = g[type].upper_bound(x);
if (g[type].count(x)) continue;
erase(x, type);
if (it != g[type].end()) upd(it->fi, type, prev);
}
for (auto &[x, id] : ask[curt]) {
int l = 0, r = 1e8 + 10, mid, ans = -1;
while (l <= r) {
mid = l + r >> 1;
int re = upper_bound(all(al), al[x] + mid) - al.begin();
int f = get(re, R);
if (f == iinf || al[f] >= al[x] - mid) ans = mid, r = mid - 1;
else l = mid + 1;
}
res[id] = ans;
}
}
for (int i = 0; i < q; ++i) cout << res[i] << '\n';
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
