#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
struct op { int time,t,x,i; };
bool comp(op a,op b) {
if (a.time == b.time) return a.t > b.t;
else return a.time < b.time;
}
vector<op> oper;
multiset<int> stores[300000];
int ans[300000];
map<int,int> M;
int query(int x) {
auto it = M.lower_bound(x);
int m = 0;
if (it != M.end()) m = max(m,it->second-(it->first-x));
if (it != M.begin()) it--,m = max(m,it->second-(x-it->first));
return m;
}
int update(int x,int h) {
//cout<<"UPDATE "<<x<<","<<h<<endl;
if (query(x) >= h) return 0;
//cout<<"XXX"<<endl;
auto it = M.lower_bound(x);
while (it != M.end()) {
if (it->second > h-(it->first-x)) break;
else it = M.erase(it);
}
M[x] = h;
it = M.find(x);
while (1) {
if (it == M.begin()) break;
it--;
if (it->second > h-(x-it->first)) break;
else it = M.erase(it);
}
return 0;
}
int main() {
int i;
int n,k,q;
int x,t,a,b,l,y;
int sub34 = 1;
scanf("%d %d %d",&n,&k,&q);
for (i = 0; i < n; i++) {
scanf("%d %d %d %d",&x,&t,&a,&b);
oper.pb((op){a,t,x,-1});
oper.pb((op){b,-t,x,-1});
sub34 &= (a == 1);
}
for (i = 0; i < q; i++) {
scanf("%d %d",&l,&y);
oper.pb((op){y,0,l,i});
}
sort(oper.begin(),oper.end(),comp);
int j;
if (sub34) {
int f = 0;
for (i = 0; i < oper.size(); i++) {
if (oper[i].t > 0) stores[oper[i].t-1].insert(oper[i].x);
else {
if (!f) {
//cout<<"here"<<endl;
for (j = 0; j < k; j++) {
stores[j].insert(-3e8);
stores[j].insert(3e8);
for (auto it = ++stores[j].begin(); it != stores[j].end(); it++) {
auto it2 = it;
it2--;
update(*it+*it2,*it-*it2);
}
}
f = 1;
//for (auto it = M.begin();it!=M.end();it++){
// cout<<it->first<<","<<it->second<<endl;
//}
}
if (oper[i].t < 0) {
int p = -oper[i].t-1;
auto it = stores[p].find(oper[i].x);
auto it2 = it;
it++,it2--;
update(*it+*it2,*it-*it2);
stores[p].erase(stores[p].find(oper[i].x));
}
else {
ans[oper[i].i] = query(2*oper[i].x)/2;
if (ans[oper[i].i] > 1e8) ans[oper[i].i] = -1;
}
}
}
}
else {
for (i = 0; i < oper.size(); i++) {
if (oper[i].t > 0) stores[oper[i].t-1].insert(oper[i].x);
else if (oper[i].t < 0) stores[-oper[i].t-1].erase(stores[-oper[i].t-1].find(oper[i].x));
else {
int m = 0;
for (j = 0; j < k; j++) {
if (stores[j].empty()) break;
else {
auto it = stores[j].lower_bound(oper[i].x);
int mm = 1e9;
if (it != stores[j].end()) mm = min(mm,*it-oper[i].x);
if (it != stores[j].begin()) mm = min(mm,oper[i].x-*(--it));
m = max(m,mm);
}
}
if (j < k) ans[oper[i].i] = -1;
else ans[oper[i].i] = m;
}
}
}
for (i = 0; i < q; i++) printf("%d\n",ans[i]);
return 0;
}
