//#define _GLIBCXX_DEBUG
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using normal_queue = priority_queue <T, vector<T>, greater<>>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define ld long double
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define eb emplace_back
template<typename T>
bool ckmn(T &x, T y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<typename T>
bool ckmx(T &x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
int bit(int x, int b) {
return (x >> b) & 1;
}
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
//soryan za musor sverhu
const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 2139062143;
const int N = 500001;
const int mod = 1e9 + 7;
const ld eps = 1e-9;
#define int ll
template<typename T>
struct SegTreeDownMax {
const T MIN = numeric_limits<T>::min() / 2;
vector <T> t;
int sz;
void init(int n, T x = numeric_limits<T>::min() / 2) {
sz = n;
t.assign(sz << 1, x);
}
void st(int i, T v) {
int x = i + sz;
t[x] = v;
x >>= 1;
while (x) {
t[x] = max(t[x << 1], t[x << 1 | 1]);
x >>= 1;
}
}
T get(int l, int r) {
l += sz;
r += sz;
// [l, r)
T ans = MIN;
while (l < r) {
if (l & 1) {
//it is a right child
ckmx(ans, t[l++]);
}
if (r & 1) {
//this is a left child
ckmx(ans, t[--r]);
}
l >>= 1;
r >>= 1;
}
return ans;
}
};
template<typename T>
struct SegTreeDownMin {
const T MAX = numeric_limits<T>::max() / 2;
vector <T> t;
int sz;
void init(int n, T x = numeric_limits<T>::max() / 2) {
sz = n;
t.assign(sz << 1, x);
}
void st(int i, T v) {
int x = i + sz;
t[x] = v;
x >>= 1;
while (x) {
t[x] = min(t[x << 1], t[x << 1 | 1]);
x >>= 1;
}
}
T get(int l, int r) { // [l, r)
T ans = MAX;
l += sz;
r += sz;
while (l < r) {
if (l & 1) {
//it is a right child
ckmn(ans, t[l++]);
}
if (r & 1) {
//this is a left child
ckmn(ans, t[--r]);
}
l >>= 1;
r >>= 1;
}
return ans;
}
};
struct Q {
int x, t, i, type;
Q(int a, int b, int c, int d) {
x = a, t = b, i = c, type = d;
}
Q() = default;
};
bool cmp(Q a, Q b) {
if (a.t != b.t) return a.t < b.t;
return a.type < b.type;
}
int x[N], a[N], b[N], t[N];
int X[N], T[N], cnt[N];
multiset<int> g[N];
ll ans[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, q;
cin >> n >> k >> q;
vector<Q> v;
vector<array<int, 4>> yy;
for (int i = 0; i < n; ++i) {
cin >> x[i] >> t[i] >> a[i] >> b[i];
--t[i];
v.emplace_back(x[i], b[i], i, 1);
v.eb(x[i], a[i], i, -1);
}
for (int i = 0; i < q; ++i) {
cin >> X[i] >> T[i];
yy.pb({X[i], -1, -1, -1});
v.eb(X[i], T[i], i, 0);
}
SegTreeDownMax<ll> stx;
SegTreeDownMin<ll> stm;
multiset<ll> L, R;
auto dod = [&](int l, int r, int i) {
int mid = (l + r) >> 1;
yy.pb({mid, l, r, i});
};
auto find = [&](int x, int type) -> int {
array nw = {x, type, -1ll, -1ll};
return lower_bound(all(yy), nw) - begin(yy);
};
auto add = [&](int l, int r, int i) {
int MMid = (l + r) >> 1;
array nw = {MMid, l, r, i};
int mid = lower_bound(all(yy), nw) - begin(yy);
stx.st(mid, r);
stm.st(mid, l);
};
auto del = [&](int l, int r, int i) {
int MMid = (l + r) >> 1;
array nw = {MMid, l, r, i};
int mid = lower_bound(all(yy), nw) - begin(yy);
stm.st(mid, stm.MAX);
stx.st(mid, stx.MIN);
};
auto addR = [&](int x, int i) {
R.insert(x);
};
auto delR = [&](int x, int i) {
R.extract(x);
};
auto addL = [&](int x, int i) {
L.insert(x);
};
auto delL = [&](int x, int i) {
L.extract(x);
};
sort(all(v), cmp);
{
int num = 0;
for (auto to: v) {
if (to.type == -1) {
int i = to.i;
auto it = g[t[i]].upper_bound(x[i]);
if (it != end(g[t[i]])) {
dod(x[i], *it, t[i]);
}
if (it != begin(g[t[i]])) {
it = prev(it);
dod(*it, x[i], t[i]);
}
g[t[i]].insert(x[i]);
++cnt[t[i]];
assert(sz(g[t[i]]) == cnt[t[i]]);
} else if (to.type == 1) {
int i = to.i;
auto it = g[t[i]].find(x[i]);
assert(it != end(g[t[i]]));
if (it != begin(g[t[i]]) && it != prev(end(g[t[i]]))) {
dod(*prev(it), *next(it), t[i]);
}
g[t[i]].erase(it);
--cnt[t[i]];
assert(sz(g[t[i]]) == cnt[t[i]]);
}
}
}
for (int i = 0; i < k; ++i) {
if (!g[i].empty()) {
assert(cnt[i]);
exit(1);
}
assert(g[i].empty());
}
assert(*max_element(all(cnt)) == 0);
sort(all(yy));
uniq(yy);
stm.init(sz(yy));
stx.init(sz(yy));
{
int num = 0;
for (auto to: v) {
if (to.type == -1) {
int i = to.i;
// for (int z : g[t[i]]) cout << z << " ";
// cout << endl;
auto &st = g[t[i]];
auto it = st.upper_bound(x[i]);
// if (it != end(g[t[i]])) {
// trace(*it)
// }
if (it != begin(g[t[i]]) && it != end(g[t[i]])) {
del(*prev(it), *it, t[i]);
}
if (it != end(st)) {
add(x[i], *it, t[i]);
} else {
if (!st.empty()) {
delR(*st.rbegin(), t[i]);
}
addR(x[i], t[i]);
}
if (it != begin(g[t[i]])) {
it = prev(it);
add(*it, x[i], t[i]);
} else {
if (!st.empty()) {
delL(*begin(st), t[i]);
}
addL(x[i], t[i]);
}
g[t[i]].insert(x[i]);
if (cnt[t[i]] == 0) ++num;
++cnt[t[i]];
} else if (to.type == 1) {
int i = to.i;
auto &st = g[t[i]];
auto it = g[t[i]].find(x[i]);
assert(it != end(g[t[i]]));
if (it == prev(end(st))) {
delR(x[i], t[i]);
if (sz(st) != 1) {
del(*prev(it), x[i], t[i]);
addR(*prev(it), t[i]);
}
}
if (it == begin(st)) {
delL(x[i], t[i]);
if (sz(st) != 1) {
del(x[i], *next(it), t[i]);
addL(*next(it), t[i]);
}
}
if (it != begin(st) && it != prev(end(st))){
del(x[i], *next(it), t[i]);
del(*prev(it), x[i], t[i]);
add(*prev(it), *next(it), t[i]);
}
g[t[i]].erase(it);
--cnt[t[i]];
if (cnt[t[i]] == 0) --num;
} else {
int i = to.i;
if (num != k) {
ans[i] = -1;
} else {
int id = find(X[i], -1);
// trace(yy[id][0])
// trace(X[i] - stm.get(id, stx.sz))
// trace(stx.get(0, id) - X[i])
// trace(X[i] - *begin(R));
// trace(*rbegin(L) - X[i])
// assert(!L.empty());
// assert(!R.empty());
// trace(id)
ans[i] = max({X[i] - stm.get(id, stx.sz), stx.get(0, id) - X[i], X[i] - *begin(R), *rbegin(L) - X[i]});
assert(ans[i] <= 100000000 && ans[i] >= 0);
}
}
}
}
for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
return 0;
}
