#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef priority_queue<pii> max_heap;
typedef priority_queue<pii, vector<pii>, greater<pii>> min_heap;
const int MX=300010, inf=1e9;
struct SHOP {
int x, type, s, e, idx;
} S[MX];
struct QUERY {
int x, t, idx, ans;
} Q[MX];
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;
// seg
struct SegTree {
int tree[4*MX]={};
multiset<int> leaf[MX];
// [0, xmax]
void init(int v=1, int s=0, int e=xmax){
tree[v]=-inf;
if(s==e) return;
init(v*2,s,(s+e)/2);
init(v*2+1,(s+e)/2+1,e);
}
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){
// cout<<"PUT: "<<x<<' '<<val<<'\n';
if(x<0 || xmax<x) return;
leaf[x].insert(val);
upt(1,0,xmax,x);
}
void pop(int x, int val){
// cout<<"POP: "<<x<<' '<<val<<'\n';
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;
Seg1.put(lo(mx), my-mx);
Seg2.put(hi(mx), my+mx);
}
void del(int x1, int x2){
int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
Seg1.pop(lo(mx), my-mx);
Seg2.pop(hi(mx), my+mx);
}
void debug(){
cout<<"\nDEBUG...\n";
cout<<"SHOPS: \n";
for(int i=1; i<=k; i++){
for(auto p:pos[i])
cout<<p<<' ';
cout<<'\n';
}
cout<<'\n';
cout<<"lines: \n";
cout<<"RAW TREE:\n";
for(int i=1; i<=4*xmax+4; i++){
cout<<Seg1.tree[i]<<' ';
}
cout<<"\nMAXES:\n";
for(int i=0; i<=xmax; i++){
cout<<i<<"- / : "<<Seg1.mx(i, i)<<", \\ : "<<Seg2.mx(i,i)<<'\n';
int a=-inf, b=-inf;
if(!Seg1.leaf[i].empty()) a=*Seg1.leaf[i].rbegin();
if(!Seg2.leaf[i].empty()) b=*Seg2.leaf[i].rbegin();
cout<<i<<"~ / : "<<a<<", \\ : "<<b<<'\n';
}
cout<<"\n";
}
int find(int qx){
if(nonzero_cnt<k) return -2;
// 1: /, 2: \
1: qx이상, max(y-x), 2: qx이하, max(y+x)
int x=lo(qx);
// cout<<Seg1.mx(x,xmax)<<" "<<Seg2.mx(0,x)<<'\n';
int ans=max(Seg1.mx(x, xmax)+qx, Seg2.mx(0, x)-qx);
// cout<<qx<<": "<<ans<<'\n';
return ans;
/*
int ans=-inf;
for(pii p:A){
int x, y; tie(x,y)=p;
if(x<qx) continue;
ans=max(ans, y-x+qx);
}
for(pii p:B){
int x, y; tie(x,y)=p;
if(x>qx) continue;
ans=max(ans, y+x-qx);
}
return ans;
*/
}
////
void add_store(int idx){
// cout<<"\nADD: "<<idx<<'\n';
multiset<int> &stores = pos[S[idx].type];
if(stores.size()==2U) nonzero_cnt++;
int x=S[idx].x;
if(stores.find(x)!=stores.end()){
stores.insert(x);
return;
}
auto it1=stores.lower_bound(x);
auto it2=stores.lower_bound(x); it2--;
int lx=*it2, rx=*it1;
del(lx, rx);
add(lx, x); add(x, rx);
stores.insert(x);
}
void del_store(int idx){
// cout<<"\nDEL: "<<idx<<'\n';
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;
}
auto it1=stores.lower_bound(x);
auto it2=stores.lower_bound(x); 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(){
min_heap in, out;
for(int i=1; i<=n; i++){
in.push({S[i].s, i});
out.push({S[i].e, i});
}
sort(Q+1, Q+q+1, [](QUERY &a, QUERY &b){ return a.t<b.t; });
init();
for(int i=1; i<=q; i++){
int qt=Q[i].t, qx=Q[i].x;
while(!in.empty()){
int t,idx; tie(t,idx)=in.top();
if(qt<t) break;
in.pop();
add_store(idx);
}
while(!out.empty()){
int t,idx; tie(t,idx)=out.top();
if(qt<=t) break;
out.pop();
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;
}
