#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5 + 5, inf = 2e9;
priority_queue<int, vector<int>, greater<int>> cur[maxn], del[maxn];
multiset<int> s[maxn];
int st[4 * maxn];
void update(int id, int l, int r, int p){
if(l == r){
while(del[p].size() && cur[p].top() == del[p].top()) cur[p].pop(), del[p].pop();
st[id] = (cur[p].empty() ? inf : cur[p].top());
}else{
int mid = (l + r) / 2;
if(p <= mid) update(id * 2, l, mid, p);
else update(id * 2 + 1, mid + 1, r, p);
st[id] = min(st[id * 2], st[id * 2 + 1]);
}
}
int query(int id, int l, int r, int u, int v){
if(v < l || r < u) return inf;
if(u <= l && r <= v) return st[id];
int mid = (l + r) / 2;
return min(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v));
}
void solve(){
int n, k, q; cin >> n >> k >> q;
vector<array<int, 4>> qry;
vector<int> cmp;
for(int i = 1; i <= n; i++){
int x, t, a, b; cin >> x >> t >> a >> b; //a,b = time. x = vị trí. t = loại
cmp.push_back(x);
qry.push_back({a, -2, x, t});
qry.push_back({b + 1, -1, x, t});
}
for(int i = 1; i <= q; i++){
int l, x; cin >> l >> x;
qry.push_back({x, i, l, 0});
}
cmp.push_back(inf);
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
sort(qry.begin(), qry.end());
auto get = [&](int x){
return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
};
vector<int> res(q + 1, -2);
for(int i = 1; i < 4 * maxn; i++) st[i] = inf;
int sz = cmp.size() - 1;
for(int i = 1; i <= k; i++){
cur[sz].push(-inf);
s[i].insert(-inf);
s[i].insert(inf);
}
update(1, 0, sz, sz);
for(auto [_, id, pos, type]: qry){
if(id == -2){
s[type].insert(pos);
auto it = s[type].find(pos);
int l = *prev(it), r = *next(it);
int pp = get(pos), rr = get(r);
cur[pp].push(l);
update(1, 0, sz, pp);
del[rr].push(l);
cur[rr].push(pos);
update(1, 0, sz, rr);
}
else if(id == -1){
auto it = s[type].find(pos);
int l = *prev(it), r = *next(it);
int pp = get(pos), rr = get(r);
del[pp].push(l);
update(1, 0, sz, pp);
cur[rr].push(l);
del[rr].push(pos);
update(1, 0, sz, rr);
s[type].erase(it);
}
else{
int l = 0, r = 1e8, ans = -1;
while(l <= r){
int mid = (l + r) / 2;
if(pos - mid <= query(1, 0, sz, get(pos + mid + 1), sz)) ans = mid, r = mid - 1;
else l = mid + 1;
}
res[id] = ans;
}
}
for(int i = 1; i <= q; i++) if(res[i] != -2) cout << res[i] << "\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
