#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ii,ii> iiii;
#define ff first
#define ss second
const int maxn = 3e5+10;
int n,k,m,o;
map<int,int> mp;
multiset<int> ms[maxn];
int b[maxn];
vector <iiii> d;
int res[maxn];
struct node
{
int wt, key, sz;
node *l, *r;
node (int x)
{
l=r=0;
sz = 1;
key = x; sz = 1;
wt = rng();
}
};
inline int get_sz(node *&x)
{
return (x)?x->sz:0;
}
inline void update(node *&x)
{
x->sz = 1 + get_sz(x->l) + get_sz(x->r);
}
void split(node *x, node *&l, node *&r, int k)
{
if (!x)
{
l=r=0;
return;
}
if (get_sz(x->l)>=k)
{
split(x->l,l,x->l,k);
r=x;
}
else
{
split(x->r,x->r,r,k-1-get_sz(x->l));
l=x;
}
update(x);
}
void split_key(node *x, node *&l, node *&r, int key)
{
if (!x)
{
l=r=0;
return;
}
if (x->key > key)
{
split_key(x->l,l,x->l,key);
r=x;
}
else
{
split_key(x->r,x->r,r,key);
l=x;
}
update(x);
}
void merg(node *&x, node *l, node *r)
{
if (!l||!r)
{
if (!l) x=r;
else x=l;
return;
}
if (l->wt > r->wt)
{
merg(l->r,l->r,r);
x=l;
}
else
{
merg(r->l,l,r->l);
x=r;
}
update(x);
}
void ins(node *&treap, int val)
{
node *a,*b;
split_key(treap,treap,a,val);
b = new node(val);
merg(treap,treap,b);
merg(treap,treap,a);
}
void dbg(node *&x)
{
if (!x) return;
dbg(x->l);
cerr<<x->key<<" :: ";
dbg(x->r);
}
void xoa(node *&treap, int val)
{
node *a, *b;
// cerr<<"xoa "<<val<<endl;
// dbg(treap); cerr<<endl;
split_key(treap,treap,a,val-1);
split(a,b,a,1);
merg(treap,treap,a);
// dbg(treap); cerr<<endl;
// cerr<<"------------"<<endl;
delete(b);
}
int lbound(node *&treap, int r)
{
node *a,*b;
// cerr<<"dbg "; dbg(treap); cerr<<endl;
split_key(treap,treap,a,r);
int ans = get_sz(a);
merg(treap,treap,a);
// cerr<<r<<" --> "<<ans<<endl;
return ans;
}
node* f[4*maxn];
int get(int x, int lx, int rx, int l, int r)
{
if (b[lx]>r||b[rx]<l) return 0;
if (b[lx]>=l&&b[rx]<=r)
{
// cerr<<"??? "<<x<<' '<<b[lx]<<' '<<b[rx]<<endl;
return lbound(f[x],r);
}
int mid=(lx+rx)/2;
return get(2*x,lx,mid,l,r) + get(2*x+1,mid+1,rx,l,r);
}
void add(int x, int lx, int rx, int idx, int val)
{
// cerr<<"+ "<<x<<' '<<b[lx]<<' '<<b[rx]<<" = "<<idx<<' '<<val<<endl;
ins(f[x],val);
// cerr<<" :) "<<endl;
if (lx==rx) return;
int mid=(lx+rx)/2;
if (idx<=b[mid]) add(2*x,lx,mid,idx,val);
else add(2*x+1,mid+1,rx,idx,val);
}
void er(int x, int lx, int rx, int idx, int val)
{
// cerr<<"- "<<x<<' '<<b[lx]<<' '<<b[rx]<<" = "<<idx<<' '<<val<<endl;
xoa(f[x],val);
// cerr<<" :< "<<endl;
if (lx==rx) return;
int mid=(lx+rx)/2;
if (idx<=b[mid]) er(2*x,lx,mid,idx,val);
else er(2*x+1,mid+1,rx,idx,val);
}
void build(int x, int lx, int rx)
{
f[x] = 0;
if (lx==rx) return;
int mid=(lx+rx)/2;
build(2*x,lx,mid); build(2*x+1,mid+1,rx);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n>>k>>m;
for (int i=1; i<=n; i++)
{
int x,t,l,r; cin>>x>>t>>l>>r;
mp[x] = 1;
d.push_back({{l,-1},{x,t}});
d.push_back({{r,1},{x,t}});
}
for (int i=1; i<=m; i++)
{
int x,l; cin>>x>>l;
d.push_back({{l,0},{x,i}});
}
sort(d.begin(),d.end());
int cnt = 0;
o = 0;
for (auto &c:mp) c.ss = ++o, b[o] = c.ff;
// cerr<<o<<endl;
build(1,1,o);
multiset<int> ms2;
for (iiii i:d)
{
// cerr<<" -- "<<i.ff.ff<<' '<<i.ff.ss<<' '<<i.ss.ff<<' '<<i.ss.ss<<" -- "<<endl;
if (i.ff.ss == -1)
{
int x = i.ss.ff; int t = i.ss.ss;
// cerr<<"pro "<<x<<endl;
if (ms[t].empty()) cnt++;
auto r = ms[t].upper_bound(x);
auto l = r;
if (l!=ms[t].begin())
{
l--;
if (r!=ms[t].end())
er(1,1,o,(*l),(*r));
else er(1,1,o,(*l),1e9);
add(1,1,o,(*l),x);
}
if (r!=ms[t].end()) add(1,1,o,x,(*r));
else add(1,1,o,x,1e9);
ms[t].insert(x);
ms2.insert(x);
// cerr<<"pri"<<endl;
}
else if (i.ff.ss == 1)
{
int x = i.ss.ff; int t = i.ss.ss;
auto j = ms[t].lower_bound(x);
auto l = j; auto r = j;
// cerr<<"notpro "<<x<<endl;
if (r==ms[t].end()) cerr<<" :@"<<endl;
r++;
if (l!=ms[t].begin())
{
l--;
er(1,1,o,(*l),x);
if (r!=ms[t].end()) add(1,1,o,(*l),(*r));
else add(1,1,o,(*l),1e9);
}
if (r!=ms[t].end()) er(1,1,o,x,(*r));
else er(1,1,o,x,1e9);
ms[t].erase(ms[t].find(x));
// cerr<<"notpri"<<endl;
if (ms[t].empty()) cnt--;
ms2.erase(ms2.find(x));
}
else
{
int x = i.ss.ff; int id = i.ss.ss;
if (cnt<k) res[id] = -1;
else
{
int l,r;
auto j = ms2.end(); j--;
r = (*j) - x;
j=ms2.begin();
r = max(r,x - (*j));
// cerr<<"? "<<x<<' '<<cnt<<" = "<<id<<endl;
l = 0;
int ans = -1;
while (l<=r)
{
int mid = l+(r-l)/2;
if (get(1,1,o,x-mid,x+mid)==k)
{
ans = mid;
r=mid-1;
}
else l=mid+1;
}
res[id] = ans;
}
}
}
for (int i=1; i<=m; i++) cout<<res[i]<<'\n';
}
/**
4 2 4
3 1 1 10
9 2 1 7
7 2 1 4
4 1 1 10
5 3
5 5
5 8
1 4
**/
