#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 6e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
struct event {
int y,id,t;
event(int _y = 0, int _id = 0, int _t = 0) {
y = _y;
id = _id;
t = _t;
}
bool operator < (const event &e) const {
return y < e.y || (y == e.y && t < e.t);
}
};
multiset <int> st[2][N << 2];
multiset <int> pos[N];
vector <event> events;
vector <int> pos_x;
int ans[N];
int _x[N];
int t[N];
int n,k,q,sz,cnt;
int getind(int x) {
return upper_bound(ALL(pos_x), x) - pos_x.begin();
}
void update(int id, int l, int r, int u, int v, int val, int t) {
if (l > v || r < u)
return;
if (l >= u && r <= v) {
if (t > 0)
st[t - 1][id].insert(val);
else
st[(-t) - 1][id].erase(st[(-t) - 1][id].find(val));
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val, t);
update(id << 1 | 1, mid + 1, r, u, v, val, t);
}
void update(int l, int r, int val, int t) {
// cerr << "update " << l << " " << r << " " << val << " " << t << "\n";
update(1, 1, sz, l, r, val, t);
}
pair <int, int> getans(int id, int l, int r, int pos) {
if (l > pos || r < pos)
return mp(oo, -oo);
int mx = -oo, mn = oo;
if (st[0][id].size())
mn = *st[0][id].begin();
if (st[1][id].size())
mx = *prev(st[1][id].end());
if (l == r)
return mp(mn, mx);
int mid = (l + r) >> 1;
pair <int, int> pir;
pir = getans(id << 1, l, mid, pos);
mini(mn, pir.fi);
maxi(mx, pir.se);
pir = getans(id << 1 | 1, mid + 1, r, pos);
mini(mn, pir.fi);
maxi(mx, pir.se);
return mp(mn, mx);
}
int getans(int x) {
int pos = getind(x);
pair <int, int> pir = getans(1, 1, sz, pos);
int minl = pir.fi;
int maxr = pir.se;
if (minl == oo && maxr == -oo)
return -1;
int res = 0;
maxi(res, pos_x[pos - 1] - minl);
maxi(res, maxr - pos_x[pos - 1]);
return res;
}
void add(int l, int r, int t) {
int mid = (l + r) >> 1;
int pl = getind(l);
int pr = getind(r);
int pmid = getind(mid);
update(pl, pmid, l, t * 1);
if (pmid < pr)
update(pmid + 1, pr, r, t * 2);
}
void solve(vector <pair <int, int>> events) {
for (pair <int, int> pir : events) {
// cerr << cnt << "\n";
int x = _x[pir.fi];
int c = t[pir.fi];
int p = getind(x);
// cerr << pir.fi << " " << pir.se << " " << x << " " << c << "\n";
if (pir.se == 2) {
ans[pir.fi - n] = (cnt < k) ? -1 : getans(x);
// cerr << "ans = " << ans[pir.fi - n] << "\n";
} else if (pir.se == 0) {
if (!pos[c].size()) {
cnt++;
update(1, p, x, 2);
update(p, sz, x, 1);
pos[c].insert(x);
continue;
}
auto it = pos[c].lower_bound(x);
if (it == pos[c].begin()) {
int tmp = getind(*it);
update(1, tmp, *it, -2);
update(1, p, x, 2);
add(x, *it, 1);
pos[c].insert(x);
continue;
}
if (it == pos[c].end()) {
it--;
int tmp = getind(*it);
update(tmp, sz, *it, -1);
update(p, sz, x, 1);
add(*it, x, 1);
pos[c].insert(x);
continue;
}
int l = *prev(it);
int r = *it;
add(l, r, -1);
add(l, x, 1);
add(x, r, 1);
pos[c].insert(x);
} else {
pos[c].erase(pos[c].find(x));
if (!pos[c].size()) {
update(1, p, x, -2);
update(p, sz, x, -1);
cnt--;
continue;
}
auto it = pos[c].lower_bound(x);
if (it == pos[c].begin()) {
int tmp = getind(*it);
update(1, tmp, *it, 2);
update(1, p, x, -2);
add(x, *it, -1);
continue;
}
if (it == pos[c].end()) {
it--;
int tmp = getind(*it);
update(tmp, sz, *it, 1);
update(p, sz, x, -1);
add(*it, x, -1);
continue;
}
int l = *prev(it);
int r = *it;
add(l, r, 1);
add(l, x, -1);
add(x, r, -1);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef ONLINE_JUDGE
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
#endif
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
int a,b;
cin >> _x[i] >> t[i] >> a >> b;
events.push_back(event(a, i, 0));
events.push_back(event(b + 1, i, 1));
pos_x.push_back(_x[i]);
}
for (int i = 1; i <= q; i++) {
int y;
cin >> _x[n + i] >> y;
events.push_back(event(y, n + i, 2));
pos_x.push_back(_x[n + i]);
}
sort(ALL(pos_x));
sz = n + q;
sort(ALL(events));
for (int l = 0; l < (int) events.size();) {
int r = l;
while (r < (int) events.size() && events[l].y == events[r].y)
r++;
vector <pair <int, int>> pir;
for (int i = l; i < r; i++)
pir.push_back(mp(events[i].id, events[i].t));
solve(pir);
l = r;
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
return 0;
}
