#include<bits/stdc++.h>
#define newl '\n'
const int N = 3e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;
struct FenwickTree{
std::vector<int> bit;
FenwickTree(int n) : bit(n + 1,0){
}
void update(int idx,int v){
for(int i = idx;i < (int)bit.size();i += (i & (-i))){
bit[i] += v;
}
}
int sum(int idx){
int ans = 0;
for(int i = idx;i > 0;i -= (i & (-i))){
ans += bit[i];
}
return ans;
}
int query(int l,int r){
// std::cerr << "1D bit query " << l << " " << r << newl;
return sum(r) - sum(l - 1);
}
};
struct FenwickTree2D{
std::vector<std::vector<int>> bit,com;
FenwickTree2D(int n) : bit(n + 1),com(n + 1){
}
void fake_update(int x,int y){
// std::cerr << "bit2d fake_update " << x << " " << y << newl;
for(int i = x;i < (int)com.size();i += (i & (-i))){
com[i].emplace_back(y);
}
}
void prepare(){
for(int i = 1;i < (int)bit.size();++i){
std::sort(com[i].begin(),com[i].end());
com[i].erase(std::unique(com[i].begin(),com[i].end()),com[i].end());
bit[i].resize(com[i].size() + 1,0);
// assert(bit[i].size() == com[i].size() + 1);
// std::cerr << "prepare " << i << " " << com[i].size() << newl;
}
// std::cerr << "ERM\n";
// std::cerr << "ERM\n";
// std::cerr << "ERM\n";
// std::cerr << "ERM\n";
// std::cerr << "ERM\n";
// std::cerr << "ERM\n";
// std::cerr << "ERM\n";
// std::cerr << "ERM\n";
}
int get(int x,int y){
return std::upper_bound(com[x].begin(),com[x].end(),y) - com[x].begin();
}
void update(int x,int y,int v){
// std::cerr << "bit2d update " << x << " " << y << " " << v << newl;
for(int i = x;i < (int)bit.size();i += (i & (-i))){
for(int j = get(i,y);j < (int)bit[i].size();j += (j & (-j))){
// std::cerr << i << " " << j << newl;
bit[i][j] += v;
}
}
}
int sum(int x,int y){
// std::cerr << "2D BIT SUM" << " " << x << " " << y << newl;
// if(x < 0){
// return 0;
// }
int ans = 0;
for(int i = x;i > 0;i -= (i & (-i))){
for(int j = get(i,y);j > 0;j -= (j & (-j))){
ans += bit[i][j];
// assert(i < (int)bit.size());
// assert(j < (int)bit[i].size());
// if(j >= (int)bit[i].size()){
//
// }
// std::cerr << "CMP " << bit[i].size() << " " << com[i].size() << newl;
// assert(bit[i].size() == com[i].size() + 1);
}
}
return ans;
}
int query(int x1,int y1,int x2,int y2){
// std::cerr << "QUERY " << x1 << " " << y1 << " " << x2 << " "<< y2 << newl;
return sum(x2,y2) - sum(x1 - 1,y2) - sum(x2,y1 - 1) + sum(x1 - 1,y1 - 1);
}
};
struct Event{
int type,x,idx;
Event(int type,int x,int idx) : type(type),x(x),idx(idx){
}
bool operator < (const Event &other) const {
return (x < other.x || (x == other.x && type < other.type));
}
};
std::vector<Event> event;
std::vector<int> com;
std::map<std::map<int,int>,int> m;
int n,k,q,x[N + 1],t[N + 1],a[N + 1],b[N + 1],l[N + 1],y[N + 1],ans[N + 1];
void readData(){
std::cin >> n >> k >> q;
for(int i = 1;i <= n;++i){
std::cin >> x[i] >> t[i] >> a[i] >> b[i];
}
for(int i = 1;i <= q;++i){
std::cin >> l[i] >> y[i];
}
}
void precompute(){
for(int i = 1;i <= n;++i){
event.emplace_back(1,a[i],i);
event.emplace_back(3,b[i],i);
}
for(int i = 1;i <= q;++i){
event.emplace_back(2,y[i],i);
}
std::sort(event.begin(),event.end());
for(int i = 1;i <= n;++i){
com.emplace_back(x[i]);
}
std::sort(com.begin(),com.end());
com.erase(std::unique(com.begin(),com.end()),com.end());
// std::cout << "COM SIZE " << (int)com.size() << newl;
}
int get(int cur_x){
return std::upper_bound(com.begin(),com.end(),cur_x) - com.begin();
}
void solve(){
// std::cout << "TEST " << get(9) << newl;
FenwickTree bit1d(n);
FenwickTree2D bit2d(n);
std::map<int,std::map<int,int>> nxt;
std::map<int,std::map<int,int>> update_queue;
std::map<int,std::set<int>> pos;
auto update_precompute = [&](){
auto fake_add = [&](int idx){
int comx = get(x[idx]);
int curt = t[idx];
++update_queue[comx][curt];
if(update_queue[comx][curt] != 1){
return;
}
std::set<int>& curs = pos[curt];
curs.insert(x[idx]);
// std::cout << "INSERT " << x[idx] << newl;
auto it = curs.lower_bound(x[idx]);
// if(it != curs.begin() && get(*prev(it)) == 0){
// std::cout << *prev(it) << newl;
// }
// if(idx == 4){
// std::cout << "BRBPATAPIM\n";
// for(int v : pos[curt]){
// std::cout << v << " ";
// }
// std::cout << newl;
// }
if(it != curs.begin()){
// std::cout << "FAKE 1 \n";
bit2d.fake_update(get(*prev(it)),x[idx]);
}
if(next(it) != curs.end()){
// std::cout << "FAKE 2 \n";
// std::cerr << "IMP " << comx << newl;
bit2d.fake_update(comx,*next(it));
}
};
auto fake_remov = [&](int idx){
int comx = get(x[idx]);
int curt = t[idx];
--update_queue[comx][curt];
if(update_queue[comx][curt] > 0){
return;
}
std::set<int>& curs = pos[curt];
auto it = curs.lower_bound(x[idx]);
if(next(it) != curs.end() && it != curs.begin()){
// std::cout << "FAKE 3 \n";
bit2d.fake_update(get(*prev(it)),*next(it));
}
curs.erase(x[idx]);
};
for(Event cur : event){
if(cur.type == 1){
fake_add(cur.idx);
}else if(cur.type == 3){
fake_remov(cur.idx);
}
}
nxt.clear();
update_queue.clear();
pos.clear();
};
auto add = [&](int idx){
int comx = get(x[idx]);
int curt = t[idx];
++update_queue[comx][curt];
if(update_queue[comx][curt] != 1){
return;
}
std::set<int>& curs = pos[curt];
curs.insert(x[idx]);
bit1d.update(comx,1);
auto it = curs.lower_bound(x[idx]);
if(it != curs.begin()){
if(next(it) != curs.end()){
bit2d.update(get(*prev(it)),*next(it),-1);
bit2d.update(get(*prev(it)),x[idx],1);
bit2d.update(comx,*next(it),1);
}else{
bit2d.update(get(*prev(it)),x[idx],1);
}
}else{
if(next(it) != curs.end()){
bit2d.update(comx,*next(it),1);
}
}
};
auto remov = [&](int idx){
int comx = get(x[idx]);
int curt = t[idx];
--update_queue[comx][curt];
if(update_queue[comx][curt] > 0){
return;
}
bit1d.update(comx,-1);
std::set<int>& curs = pos[curt];
auto it = curs.lower_bound(x[idx]);
if(it != curs.begin()){
if(next(it) != curs.end()){
bit2d.update(get(*prev(it)),x[idx],-1);
bit2d.update(comx,*next(it),-1);
bit2d.update(get(*prev(it)),*next(it),1);
}else{
bit2d.update(get(*prev(it)),x[idx],-1);
}
}else{
if(next(it) != curs.end()){
bit2d.update(comx,*next(it),-1);
}
}
curs.erase(x[idx]);
};
update_precompute();
bit2d.prepare();
for(Event cur : event){
auto f = [&](int l,int r){
int coml = get(l);
int comr = get(r);
// std::cout << l << " " << r << " " << bit2d.query(coml,1,comr,r) << newl;
return bit1d.query(coml,comr) - bit2d.query(coml,1,comr,r);
};
if(cur.type == 1){
add(cur.idx);
}else if(cur.type == 3){
remov(cur.idx);
}else{
int lo = 0,hi = 1e8,cur_ans = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
int ll = std::max(1,l[cur.idx] - mid);
int rr = std::min((int)1e8,l[cur.idx] + mid);
if(f(ll,rr) == k){
cur_ans = mid;
hi = mid - 1;
}else{
lo = mid + 1;
}
}
ans[cur.idx] = cur_ans;
}
// std::cout << "IMP " << f(1,n) << newl;
}
}
void print_answer(){
for(int i = 1;i <= q;++i){
std::cout << ans[i] << newl;
}
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
readData();
precompute();
solve();
print_answer();
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
5 10
*/
