#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ld double
#define ll __int128
mt19937 rnd(51);
const int INF = 1e9;
struct st{
vector<int> t_min, t_max;
vector<multiset<int>> t;
void build(int n) {
t_min.clear(), t_max.clear(), t.clear();
t_min.resize(4 * n, INF);
t_max.resize(4 * n, -INF);
t.resize(4 * n);
}
void upd(int v) {
if (t[v].size() == 0) {
t_min[v] = INF;
t_max[v] = -INF;
return;
}
t_min[v] = *t[v].begin();
t_max[v] = *t[v].rbegin();
}
void update(int v, int l, int r, int pos, int val, int add) {
if (l == r) {
if (add) {
t[v].insert(val);
} else {
t[v].erase(t[v].find(val));
}
upd(v);
return;
}
int m = (l + r) / 2;
if (pos <= m) {
update(2 * v, l, m, pos, val, add);
} else {
update(2 * v + 1, m + 1, r, pos, val, add);
}
t_min[v] = min(t_min[v * 2], t_min[v * 2 + 1]);
t_max[v] = max(t_max[v * 2], t_max[v * 2 + 1]);
}
int get_min(int v, int tl, int tr, int l, int r) {
if (l > r) return INF;
if (tl == l && tr == r) {
return t_min[v];
}
int tm = (tl + tr) / 2;
return min(get_min(2 * v, tl, tm, l, min(r, tm)), get_min(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
int get_max(int v, int tl, int tr, int l, int r) {
if (l > r) return -INF;
if (tl == l && tr == r) {
return t_max[v];
}
int tm = (tl + tr) / 2;
return max(get_max(2 * v, tl, tm, l, min(r, tm)), get_max(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
};
vector<multiset<int>> pos;
vector<int> u2;
st L, R;
int sz;
void add(int a, int b) {
int need = (a + b) / 2;
int pos = upper_bound(u2.begin(), u2.end(), need) - u2.begin() - 1;
int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
L.update(1, 0, sz - 1, pos, a, 1);
R.update(1, 0, sz - 1, pos + 1, b, 1);
}
void del(int a, int b) {
int need = (a + b) / 2;
int pos = upper_bound(u2.begin(), u2.end(), need) - u2.begin() - 1;
int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
L.update(1, 0, sz - 1, pos, a, 0);
R.update(1, 0, sz - 1, pos + 1, b, 0);
}
void func(int i, int j, int need) {
if (need) {
if (pos[i].find(j) != pos[i].end()) {
pos[i].insert(j);
return;
}
int pre = *prev(pos[i].lower_bound(j));
int nxt = *pos[i].upper_bound(j);
del(pre, nxt);
add(pre, j);
add(j, nxt);
pos[i].insert(j);
} else {
pos[i].erase(pos[i].find(j));
if (pos[i].find(j) != pos[i].end()) return;
int pre = *prev(pos[i].lower_bound(j));
int nxt = *pos[i].upper_bound(j);
del(pre, j);
del(j, nxt);
add(pre, nxt);
}
}
vector<int> solve(int n, int k, int q, vector<int> x, vector<int> t, vector<int> a, vector<int> b, vector<int> l, vector<int> y) {
u2.clear();
u2.pb(-INF);
u2.pb(INF);
vector<vector<int>> ind(k);
pos.clear();
pos.resize(k);
vector<int> ans(q);
for (int i = 0; i < n; i++) {
ind[t[i]].pb(x[i]);
u2.pb(x[i]);
}
for (int i = 0; i < k; i++) {
ind[i].pb(-INF);
ind[i].pb(INF);
sort(ind[i].begin(), ind[i].end());
for (int j = 0; j + 1 < ind[i].size(); j++) {
u2.pb({(ind[i][j] + ind[i][j + 1]) / 2});
}
}
for (int i = 0; i < q; i++) {
u2.pb(l[i]);
}
sort(u2.begin(), u2.end());
u2.erase(unique(u2.begin(), u2.end()), u2.end());
vector<vector<int>> qu;
for (int i = 0; i < n; i++) {
qu.pb({a[i], -1, t[i], x[i]});
qu.pb({b[i], 1, t[i], x[i]});
}
for (int i = 0; i < q; i++) {
qu.pb({y[i], 0, l[i], i});
}
sz = u2.size();
bool bad = 0;
L.build(sz);
R.build(sz);
for (int i = 0; i < k; i++) {
if (ind[i].size() == 2) bad = 1;
pos[i].insert(-INF);
pos[i].insert(INF);
add(-INF, INF);
}
sort(qu.begin(), qu.end());
set<int> st;
for (int i = 0; i < k; i++) st.insert(i);
for (int i = 0; i < qu.size(); i++) {
if (qu[i][1] == -1) {
if (pos[qu[i][2]].size() == 2) st.erase(qu[i][2]);
func(qu[i][2], qu[i][3], 1);
} else if (qu[i][1] == 0) {
int j = lower_bound(u2.begin(), u2.end(), qu[i][2]) - u2.begin();
int mx = L.get_min(1, 0, sz - 1, j, sz - 1), mn = R.get_max(1, 0, sz - 1, 0, j);
if (st.size() > 0) {
ans[qu[i][3]] = -1;
} else {
ans[qu[i][3]] = max(qu[i][2] - mx, mn - qu[i][2]);
}
} else {
func(qu[i][2], qu[i][3], 0);
if (pos[qu[i][2]].size() == 2) st.insert(qu[i][2]);
}
}
return ans;
}
vector<int> solvee(int n, int k, int q, vector<int> x, vector<int> t, vector<int> a, vector<int> b, vector<int> l, vector<int> y) {
vector<int> ans;
for (int i = 0; i < q; i++) {
vector<int> bst(k, INF);
for (int j = 0; j < n; j++) {
if (a[j] <= y[i] && y[i] <= b[j]) {
bst[t[j]] = min(bst[t[j]], abs(x[j] - l[i]));
}
}
if (*max_element(bst.begin(), bst.end()) == INF) ans.pb(-1);
else ans.pb(*max_element(bst.begin(), bst.end()));
}
return ans;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
if (1) {
int n, k, q;
cin >> n >> k >> q;
vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
for (int i = 0; i < n; i++) {
cin >> x[i] >> t[i] >> a[i] >> b[i];
t[i]--;
}
for (int i = 0; i < q; i++) {
cin >> l[i] >> y[i];
}
vector<int> ans = solve(n, k, q, x, t, a, b, l, y);
for (auto to : ans) {
cout << to << '\n';
}
return 0;
}
while (1) {
int n = rnd() % 5 + 1, k = rnd() % 5 + 1, q = rnd() % 1 + 1;
vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
for (int i = 0; i < n; i++) {
x[i] = rnd() % 10 + 1;
t[i] = rnd() % k;
a[i] = rnd() % 10 + 1;
b[i] = rnd() % 10 + 1;
if (a[i] > b[i]) swap(a[i], b[i]);
}
for (int i = 0; i < q; i++) {
l[i] = rnd() % 10 + 1;
y[i] = rnd() % 10 + 1;
}
auto res = solve(n, k, q, x, t, a, b, l, y), res2 = solvee(n, k, q, x, t, a, b, l, y);
if (res != res2) {
cout << n << ' ' << k << ' ' << q << endl;
for (int i = 0; i < n; i++) {
cout << x[i] << ' ' << t[i] + 1 << ' ' << a[i] << ' ' << b[i] << endl;
}
for (int i = 0; i < q; i++) {
cout << l[i] << ' ' << y[i] << endl;
}
cout << "Bad" << endl;
for (int i = 0; i < q; i++) {
cout << res[i] << ' ' << res2[i] << endl;
}
return 0;
}
cout << "ok" << endl;
}
return 0;
}
