#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
using namespace std ;
const int inf = 1e9 ;
const int MAX = 3e5 + 10 ;
int ans[MAX] ;
int n , k , q ;
multiset<int>s[MAX] ;
vector<int>v ;
vector< array<int , 4> >queries ;
int tree[4 * MAX] ;
multiset<int>vals[4 * MAX] ;
void update(int node , int l , int r , int idx , int val)
{
if(idx > r || idx < l)
return ;
if(l == r)
{
if(val < 0)
vals[node].erase(vals[node].find(-1 * val)) ;
else
vals[node].insert(val) ;
if(vals[node].size())
tree[node] = *vals[node].rbegin() ;
else
tree[node] = 0 ;
return ;
}
int mid = (l + r) >> 1 ;
update(node << 1 , l , mid , idx , val) ;
update(node << 1 | 1 , mid+1 , r , idx , val) ;
tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}
int query(int node , int l , int r , int from , int to)
{
if(from > r || to < l)
return 0 ;
if(l >= from && r <= to)
return tree[node] ;
int mid = (l + r) >> 1 ;
int x = query(node << 1 , l , mid , from , to) ;
int y = query(node << 1 | 1 , mid+1 , r , from , to) ;
return max(x , y) ;
}
bool cmp(array<int , 4>&a , array<int , 4>&b)
{
if(a[0] != b[0])
return a[0] < b[0] ;
else
return a[3] < b[3] ;
}
int getidx(int x)
{
return lower_bound(v.begin() , v.end() , x) - v.begin() ;
}
void Add(int x , int t)
{
int prv = *prev(s[t].lower_bound(x)) ;
int nxt = *s[t].lower_bound(x) ;
update(1 , 0 , n , getidx(prv) , -1 * nxt) ;
update(1 , 0 , n , getidx(prv) , x) ;
update(1 , 0 , n , getidx(x) , nxt) ;
s[t].insert(x) ;
}
void Erase(int x , int t)
{
s[t].erase(s[t].find(x)) ;
int prv = *prev(s[t].lower_bound(x)) ;
int nxt = *s[t].lower_bound(x) ;
update(1 , 0 , n , getidx(prv) , -1 * x) ;
update(1 , 0 , n , getidx(prv) , nxt) ;
update(1 , 0 , n , getidx(x) , -1 * nxt) ;
}
bool check(int x , int y)
{
int idx = lower_bound(v.begin() , v.end() , x - y) - v.begin() ;
idx-- ;
idx = max(idx , 0) ;
return (query(1 , 0 , n , 0 , idx) <= x + y) ;
}
int solve(int x)
{
int l = 0 , r = 1e8 ;
int ans = -1 ;
while(l <= r)
{
int mid = (l + r) >> 1 ;
if(check(x , mid))
ans = mid , r = mid-1 ;
else
l = mid+1 ;
}
return ans ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>k>>q ;
for(int i = 0 ; i < n ; ++i)
{
int x , t , a , b ;
cin>>x>>t>>a>>b ;
queries.push_back({a , x , t , 0}) ;
queries.push_back({b+1 , x , t , -1}) ;
v.push_back(x) ;
}
for(int i = 0 ; i < q ; ++i)
{
int x , y ;
cin>>x>>y ;
queries.push_back({y , x , i , 1}) ;
}
v.push_back(0) ;
sort(v.begin() , v.end()) ;
v.erase(unique(v.begin() , v.end()) , v.end()) ;
sort(queries.begin() , queries.end() , cmp) ;
for(int i = 1 ; i <= k ; ++i)
s[i].insert(0) , s[i].insert(inf) , update(1 , 0 , n , 0 , inf) ;
for(auto &a : queries)
{
if(a[3] == 0)
Add(a[1] , a[2]) ;
else if(a[3] == -1)
Erase(a[1] , a[2]) ;
else
ans[a[2]] = solve(a[1]) ;
}
for(int i = 0 ; i < q ; ++i)
cout<<ans[i]<<"\n" ;
return 0 ;
}
