#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef multiset<int>::iterator mit;
const int MX=300010, inf=1<<29;
struct SHOP {
int x, type, s, e, idx;
} S[MX];
struct QUERY {
int x, t, idx, ans;
} Q[MX];
inline int max(int x, int y){ return x>y ? x : y; }
int n, q, k;
void input(){
cin>>n>>k>>q;
for(int i=1; i<=n; i++){
int t, x, s, e;
cin>>x>>t>>s>>e;
S[i]={x,t,s,e,i};
}
for(int i=1; i<=q; i++){
int x, t;
cin>>x>>t;
Q[i]={x,t,i};
}
}
vector<int> X;
int xmax;
int lo(int x){
return upper_bound(X.begin(), X.end(), x)-X.begin()-1;
}
int hi(int x){
return lower_bound(X.begin(), X.end(), x)-X.begin();
}
void prec(){
for(int i=1; i<=n; i++){
S[i].x*=2;
}
for(int i=1; i<=q; i++){
Q[i].x*=2;
X.push_back(Q[i].x);
}
sort(X.begin(), X.end());
X.resize(unique(X.begin(), X.end())-X.begin());
xmax=X.size()-1U;
}
//////
multiset<int> pos[MX];
int nonzero_cnt;
struct SegTree {
int tree[4*MX]={};
multiset<int> leaf[MX];
// [0, xmax]
void init(){
for(int i=1; i<=4*xmax; i++) tree[i]=-inf;
}
int mx(int v, int s, int e, int l, int r){
if(r<s || e<l) return -inf;
if(l<=s && e<=r) return tree[v];
return max(mx(v*2, s, (s+e)/2, l, r), mx(v*2+1, (s+e)/2+1, e, l, r));
}
int mx(int l, int r){
return mx(1,0,xmax,l,r);
}
void upt(int v, int s, int e, int x){
if(x<s || e<x) return;
if(s==e){
if(leaf[x].empty()) tree[v]=-inf;
else tree[v]=*leaf[x].rbegin();
return;
}
upt(v*2, s, (s+e)/2, x);
upt(v*2+1, (s+e)/2+1, e, x);
tree[v]=max(tree[v*2], tree[v*2+1]);
}
void put(int x, int val){
if(x<0 || xmax<x) return;
leaf[x].insert(val);
upt(1,0,xmax,x);
}
void pop(int x, int val){
if(x<0 || xmax<x) return;
leaf[x].erase(leaf[x].find(val));
upt(1,0,xmax,x);
}
} Seg1, Seg2;
// 1이 /, 2가 \
//1: max(y-x), 2: max(y+x)
void add(int x1, int x2){
int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
int pos=hi(mx);
Seg1.put(pos-1, my-mx);
Seg2.put(pos, my+mx);
}
void del(int x1, int x2){
int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
int pos=hi(mx);
Seg1.pop(pos-1, my-mx);
Seg2.pop(pos, my+mx);
}
int find(int qx){
if(nonzero_cnt<k) return -2;
int x=lo(qx);
int ans=max(Seg1.mx(x, xmax)+qx, Seg2.mx(0, x)-qx);
return ans;
}
////
void add_store(int idx){
multiset<int> &stores = pos[S[idx].type];
if(stores.size()==2U) nonzero_cnt++;
int x=S[idx].x;
if(stores.find(x)==stores.end()){
mit it1=stores.lower_bound(x), it2=it1; it2--;
int lx=*it2, rx=*it1;
del(lx, rx);
add(lx, x); add(x, rx);
}
stores.insert(x);
}
void del_store(int idx){
multiset<int> &stores = pos[S[idx].type];
if(stores.size()==3U) nonzero_cnt--;
int x=S[idx].x;
stores.erase(stores.find(x));
if(stores.find(x)!=stores.end())
return;
mit it1=stores.lower_bound(x), it2=it1; it2--;
int lx=*it2, rx=*it1;
del(lx, x); del(x, rx);
add(lx, rx);
}
void init(){
Seg1.init();
Seg2.init();
for(int i=1; i<=k; i++){
pos[i].insert(inf);
pos[i].insert(-inf);
add(-inf, inf);
}
}
void solve(){
vector<pii> in, out;
for(int i=1; i<=n; i++){
in.push_back({S[i].s, i});
out.push_back({S[i].e, i});
}
sort(Q+1, Q+q+1, [](QUERY &a, QUERY &b){ return a.t<b.t; });
sort(in.begin(), in.end());
sort(out.begin(), out.end());
init();
for(int i=1, a=0, b=0; i<=q; i++){
int qt=Q[i].t, qx=Q[i].x;
while(a<n){
int t,idx; tie(t,idx)=in[a];
if(qt<t) break;
a++;
add_store(idx);
}
while(b<n){
int t,idx; tie(t,idx)=out[b];
if(qt<=t) break;
b++;
del_store(idx);
}
Q[i].ans=find(qx);
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
input();
prec();
solve();
sort(Q+1, Q+q+1, [](QUERY &a, QUERY &b){ return a.idx<b.idx; });
for(int i=1; i<=q; i++){
cout<<Q[i].ans/2<<'\n';
}
return 0;
}
