#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=300007,pot=1<<19;

multiset<int>S[N];
int X[N],t[N],A[N],B[N];

int it=0;
int M[100000007];
int last[100000007];

int get(int x)
{
	if(x==2*inf) return it;
	if(x==-inf) return 1;
	return M[x];
}

int ans[N];

int seg[2*pot+7];
multiset<int>W[N];

int que(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return seg[v];
	if(r<a||l>b) return 0;
	return max(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}

void add(int l,int r)
{
	W[l].insert(r);
	int v=l+pot-1;
	seg[v]=*--W[l].end();
	while(v>1)
	{
		v/=2;
		seg[v]=max(seg[2*v],seg[2*v+1]);
	}
}
void del(int l,int r)
{
	W[l].erase(W[l].find(r));
	int v=l+pot-1;
	seg[v]=*--W[l].end();
	while(v>1)
	{
		v/=2;
		seg[v]=max(seg[2*v],seg[2*v+1]);
	}
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k,q;
	cin>>n>>k>>q;
	set<int>T;
	T.insert(-inf);
	T.insert(2*inf);
	FOR(i,1,n)
	{
		cin>>X[i]>>t[i]>>A[i]>>B[i];
		T.insert(X[i]);
	}
	for(auto x:T) 
	{
		it++;
		if(x!=2*inf&&x!=-inf) M[x]=it;
	}
	FOR(i,1,100000000) 
	{
		if(M[i]) last[i]=i;
		else last[i]=last[i-1];
	}
	FOR(i,1,it) W[i].insert(0);
	FOR(i,1,k)
	{
		S[i].insert(-inf);
		S[i].insert(2*inf);
		add(get(-inf),get(2*inf));
	}
	vector<pair<pair<int,int>,pair<int,int>>>E;
	FOR(i,1,n)
	{
		E.pb({{A[i],0},{X[i],t[i]}});
		E.pb({{B[i]+1,-1},{X[i],t[i]}});
	}
	FOR(i,1,q)
	{
		int l,y;
		cin>>l>>y;
		E.pb({{y,1},{l,i}});
	}
	sort(all(E));
	for(auto [p,q]:E)
	{
		if(p.nd==-1)
		{
			debug("del",q.st,q.nd);
			S[q.nd].erase(S[q.nd].find(q.st));
			int x=*--S[q.nd].lower_bound(q.st);
			int y=*S[q.nd].lower_bound(q.st);
			int x1=get(x),x2=get(q.st),x3=get(y);
			del(x1,x2);
			del(x2,x3);
			add(x1,x3);
		}
		else if(p.nd==0)
		{
			debug("add",q.st,q.nd);
			int x=*--S[q.nd].lower_bound(q.st);
			int y=*S[q.nd].lower_bound(q.st);
			S[q.nd].insert(q.st);
			int x1=get(x),x2=get(q.st),x3=get(y);
			add(x1,x2);
			add(x2,x3);
			del(x1,x3);
		}
		else
		{
			debug("que",q.st,q.nd);
			ans[q.nd]=-1;
			int l=0,r=100000000,sr;
			while(l<=r)
			{
				sr=(l+r)/2;
				int lx=q.st-sr,rx=q.st+sr;
				lx=get(*T.lower_bound(lx));
				rx=get(last[min(rx,100000000)]);
				debug(lx,rx);
				if(lx<=rx&&que(1,1,lx-1,1,pot)<=rx)
				{
					ans[q.nd]=sr;
					r=sr-1;
				}
				else l=sr+1;
			}
		}
	}
	FOR(i,1,q) cout<<ans[i]<<endl;
	
	return 0;
}