#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(x) (int)(x).size()
#define BIT(mask , x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))
template<class T1,class T2>
bool maximize(T1 &a,T2 b){
if (a < b) return a = b , true; else return false;
}
template<class T1,class T2>
bool minimize(T1 &a,T2 b){
if (a > b) return a = b , true; else return false;
}
template<class T1>
void compress(vector<T1>&data){
sort(data.begin() , data.end());
data.resize(unique(data.begin() , data.end()) - data.begin());
}
template<class T1,class T2>
int Find(vector<T1>&data,T2 x){
return upper_bound(data.begin() , data.end() , x) - data.begin();
}
const int N = (int) 3e5;
const int inf = (int)1e9;
int n , k , q;
int x[N + 2] , t[N + 2] , a[N + 2] , b[N + 2];
struct Question{
int l,y;
void read(){
cin >> l >> y;
}
} queri[N + 2];
namespace subtask1{
bool check(){
return k <= 400;
}
const int MAXN = (int) N * 3;
vector<int>nen;
vector<pair<int,int>>open[MAXN + 2] , close[MAXN + 2] , ask[MAXN + 2];
multiset<int>st[N+2];
int cnt[MAXN + 2] = {};
int ans[N + 2] = {};
void main_code(){
for(int i = 1; i <= n; ++i) {
nen.push_back(a[i]) ,
nen.push_back(b[i]);
}
for(int i = 1; i <= q; ++i) nen.push_back(queri[i].y);
compress(nen);
for(int i = 1; i <= n; ++i){
a[i] = Find(nen , a[i]) , b[i] = Find(nen , b[i]);
open[a[i]].push_back({x[i] , t[i]});
close[b[i]].push_back({x[i] , t[i]});
}
for(int i = 1; i <= q; ++i){
queri[i].y = Find(nen , queri[i].y);
ask[queri[i].y].push_back({queri[i].l , i});
ans[i] = 0;
}
int full = 0;
for(int i = 1; i <= sz(nen); ++i){
for(auto x : open[i]) {
//... setalize
full -= (cnt[x.second] > 0);
cnt[x.second]++;
full += (cnt[x.second] > 0);
st[x.second].insert(x.first);
}
for(auto x : ask[i]){
if (full != k) ans[x.second] = -1;
else {
for(int j = 1; j <= k; ++j){
auto t1 = st[j].lower_bound(x.first);
int res = inf;
if (t1!=st[j].end()) minimize(res , abs(*t1 - x.first));
if (t1!=st[j].begin()){
--t1;
minimize(res , abs(*t1 - x.first));
}
maximize(ans[x.second] , res);
}
}
}
for(auto x : close[i]) {
//... setalize
full -= (cnt[x.second] > 0);
cnt[x.second]--;
full += (cnt[x.second] > 0);
st[x.second].erase(st[x.second].find(x.first));
}
}
for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
}
namespace subtask2{
bool check(){
for(int i = 1; i <= n; ++i) if (a[i] != 1 || b[i] != (int)1e8) return false;
return true;
}
vector<int>nen;
class IT{
public:
vector<int> st_max , st_min;
vector<int> lazy_max , lazy_min;
void load_size(int n){
st_max = lazy_max = vector<int>(n * 4 + 2 , 0);
st_min = lazy_min = vector<int>(n * 4 + 2 , inf);
}
void pushdown(int id){
int &t1 = lazy_max[id] , &t2 = lazy_min[id];
maximize(st_max[id * 2] , t1);
maximize(st_max[id * 2 + 1] , t1);
minimize(st_min[id * 2] , t2);
minimize(st_min[id * 2 + 1] , t2);
maximize(lazy_max[id * 2] , t1);
maximize(lazy_max[id * 2 + 1] , t1);
minimize(lazy_min[id * 2] , t2);
minimize(lazy_min[id * 2 + 1] , t2);
return;
}
void update(int id , int l , int r , int u , int v , int val){
if (l > v || r < u) return ;
if (u <= l && r <= v){
st_max[id] = max(st_max[id] , val);
st_min[id] = min(st_min[id] , val);
lazy_max[id] = max(lazy_max[id] , val);
lazy_min[id] = min(lazy_min[id] , val);
return;
}
int m = (l + r) / 2;
pushdown(id);
update(id * 2 , l , m , u , v , val);
update(id * 2 + 1 , m + 1 , r , u , v , val);
st_max[id] = max(st_max[id * 2] , st_max[id * 2 + 1]);
st_min[id] = min(st_min[id * 2] , st_min[id * 2 + 1]);
return;
}
int Get_max(int id , int l , int r , int u , int v){
if (l > v || r < u) return 0;
if (u <= l && r <= v) return st_max[id];
int m = (l + r) / 2;
pushdown(id);
return max(Get_max(id * 2 , l , m , u , v) , Get_max(id * 2 + 1 , m + 1 , r , u , v));
}
int Get_min(int id , int l , int r , int u , int v){
if (l > v || r < u) return inf;
if (u <= l && r <= v) return st_min[id];
int m = (l + r) / 2;
pushdown(id);
return min(Get_min(id * 2 , l , m , u , v) , Get_min(id * 2 + 1 , m + 1 , r , u , v));
}
};
IT st;
vector<int>arr[N + 2];
int Find_index(vector<int>&data , int l , int bound , int nxt_bound){
int low = l , high = sz(data) - 1 , pos = l - 1;
while (low <= high){
int mid = (low + high) / 2;
if (abs(data[mid] - bound) <= abs(data[mid] - nxt_bound)){
pos = mid;
low = mid + 1;
}
else high = mid - 1;
}
return pos;
}
void main_code(){
bool ok = true;
for(int i = 1; i <= n; ++i) arr[t[i]].push_back(x[i]);
for(int i = 1; i <= k; ++i) compress(arr[i]);
vector<int>v;
for(int i = 1; i <= q; ++i) v.push_back(queri[i].l);
compress(v);
st.load_size(sz(v));
// for(auto& x : v) cout << x << ' '; cout << '\n';
for(int i = 1; i <= k; ++i){
int cur = 0;
for(int j = 0 ; j < sz(arr[i]); ++j){
if (j + 1 == sz(arr[i])) st.update(1 , 0 , sz(v) - 1 , cur , sz(v) - 1 , arr[i][j]);
else {
int nxt = Find_index(v , cur , arr[i][j] , arr[i][j + 1]);
st.update(1 , 0 , sz(v) - 1 , cur , nxt , arr[i][j]);
// if (i==2){
// cout << cur << ' ' << nxt << ' ' << arr[i][j] << ' ' << arr[i][j + 1] << '\n';
// }
cur = nxt + 1;
}
}
ok &= (sz(arr[i]) > 0);
}
for(int i = 1; i <= q; ++i){
// if (i != 4) continue;
int t = Find(v , queri[i].l) - 1;
int x = st.Get_max(1 , 0 , sz(v) - 1 , t , t) ;
int y = st.Get_min(1 , 0 , sz(v) - 1 , t , t) ;
// cout << x << ' ' << y << ' ' << t << '\n';
if (ok==false) cout<<-1<<'\n'; else
cout << max(abs(queri[i].l - x) , abs(queri[i].l - y)) << '\n';
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0) ;
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> n >> k >> q;
for(int i = 1; i <= n; ++i) cin >> x[i] >> t[i] >> a[i] >> b[i];
for(int i = 1; i <= q; ++i) queri[i].read();
if (subtask1::check()) return subtask1::main_code() , 0;
return subtask2::main_code() , 0;
assert(false);
return 0;
}
