/*
Playing the sand
Holding your hand
Cause I remember every sunset
I remember every word you said
*/
#include <bits/stdc++.h>
#define lp(i,a,b) for(int i = a; i < b ; i++)
#define ff first
#define ss second
#define pb emplace_back
#define ll long long
#define mk make_pair
#define sz(x) (int)(x.size())
#define pii pair<int,int>
#define mkt make_tuple
#define debug
#define all(x) x.begin(),x.end()
const int MAX = 3e5+10 ;
const int MAX_COORD = 1e8+10 ;
using namespace std ;
struct Event
{
int type , x, id , xIntercept ;
Event(int type = 0 , int x = 0 , int id = 0 , int xIntercept = 0 ) : type(type) , x(x) , id(id) , xIntercept(xIntercept) {}
bool operator < (Event other) const
{
if(x == other.x ) return type < other.type ;
return x < other.x ;
}
};
int N , K , Q ;
int mxNegative, mnPositive = MAX_COORD ;
int ansQuery[MAX] ;
vector<int> store[MAX] ;
vector< pair<int,int> > lines ;
vector<Event> sweepPositive, sweepNegative ;
void add(int slope , int beg, int en )
{
debug("Adding the so-called line %d %d %d\n" , slope , beg, en ) ;
if( slope == -1 ) sweepNegative.emplace_back( Event(0, beg , 0 , en) ) ;
else sweepPositive.emplace_back( Event(1,en , 0 , beg ) ) ;
}
void impossible()
{
for(int i = 1 ; i <= Q ; i++ ) printf("-1\n") ;
exit(0) ;
}
int main()
{
scanf("%d%d%d", &N , &K , &Q );
for(int i = 1 ; i <= N ; i++ )
{
int location , shop , year1, year2 ;
scanf("%d%d%d%d", &location , &shop, &year1, &year2 ) ;
assert( year1 == 1 && year2 == 100000000 ) ;
store[ shop ].emplace_back( location ) ;
}
for(int i = 1 , x , year ; i <= Q ; i++ )
{
scanf("%d%d", &x, &year ) ;
sweepNegative.emplace_back( Event(1,x,i, 0) ) ;
sweepPositive.emplace_back( Event(0, x, i, 0) ) ;
}
for(int i = 1 ; i <= K ; i++ )
{
if( sz(store[i]) == 0 ) impossible() ;
sort( all(store[i]) ) ;
int storeSize = sz(store[i]) ;
//Let's add all negative slopes first
add( -1 , -1 , store[i][0] ) ;
for(int j = 1 ; j < sz(store[i]) ; j++ )
add(-1, ceil( (1.0*store[i][j] + 1.0*store[i][j-1])/2.0 ) , store[i][j] ) ;
//Now let's add positive slopes
add(1, store[i][ storeSize-1 ] , MAX_COORD) ;
for(int j = storeSize-2 ; j >= 0 ; j-- )
add(1, store[i][j] , (store[i][j]+store[i][j+1])/2 ) ;
}
sort( all(sweepNegative) ) ;
sort( all(sweepPositive) ) ;
reverse( all(sweepPositive) ) ;
for(auto e : sweepNegative)
{
if( e.type == 0 )
{
mxNegative = max( mxNegative, e.xIntercept ) ;
continue ;
}
ansQuery[ e.id ] = max( ansQuery[e.id] , mxNegative - e.x ) ;
}
for(auto e : sweepPositive )
{
if( e.type == 1 )
{
mnPositive = min( mnPositive, e.xIntercept ) ;
continue ;
}
ansQuery[e.id] = max( ansQuery[e.id] , e.x - mnPositive ) ;
}
for(int i = 1 ; i <= Q ; i++ ) printf("%d\n", ansQuery[i] ) ;
}
