#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
using namespace std;
const int MAXN = 300000;
const int MAXI = 1048576;
const int INF = 100000000;
int n, k, q, bp;
vector<int> com;
inline int idx(int x)
{
return lower_bound(com.begin(), com.end(), x) - com.begin();
}
struct eve1
{
int t, x, d;
bool operator <(const eve1 &e) const
{
return t != e.t ? t < e.t : d > e.d;
}
};
struct ent1
{
int c, l, lt, r, rt;
};
vector<eve1> arr1;
map<int, ent1> loc1[MAXN + 10];
// add : t time, p = 1, [x -> y] loc, d origin
// query: t time, p = 2, x loc, y idx, d = -1
// sub : t time, p = 3, [x -> y] loc, d origin
struct eve2
{
int t, p, x, y, d;
bool operator <(const eve2 &e) const
{
return t != e.t ? t < e.t : p < e.p;
}
};
vector<eve2> arr2;
void add_seg(int t, int t2, int x, int y)
{
if(t > t2 || x == y)
return;
int nx = bp + idx(min(x, y));
int ny = bp + idx(max(x, y) + 1) - 1;
if(nx > ny)
return;
arr2.push_back({ t, 1, nx, ny, x });
arr2.push_back({ t2, 3, nx, ny, x });
}
struct ent2
{
priority_queue<int> pq1, pq2, rpq1, rpq2;
};
ent2 mem2[MAXI + 10];
void upd(int x, int p, int d)
{
if(p == 1)
{
mem2[x].pq1.push(d);
mem2[x].pq2.push(-d);
}
else
{
mem2[x].rpq1.push(d);
mem2[x].rpq2.push(-d);
}
}
void add_mem(const eve2 &e)
{
int x = e.x;
int y = e.y;
while(x < y)
{
if(x % 2 == 1)
{
upd(x, e.p, e.d);
x++;
}
if(y % 2 == 0)
{
upd(y, e.p, e.d);
y--;
}
x /= 2;
y /= 2;
}
if(x == y)
upd(x, e.p, e.d);
}
int get_mem(int p)
{
int r = 0;
int x = bp + idx(p);
while(x)
{
while(!mem2[x].pq1.empty() && !mem2[x].rpq1.empty() && mem2[x].pq1.top() == mem2[x].rpq1.top())
{
mem2[x].pq1.pop();
mem2[x].rpq1.pop();
}
if(!mem2[x].pq1.empty())
r = max(r, abs(p - mem2[x].pq1.top()));
while(!mem2[x].pq2.empty() && !mem2[x].rpq2.empty() && mem2[x].pq2.top() == mem2[x].rpq2.top())
{
mem2[x].pq2.pop();
mem2[x].rpq2.pop();
}
if(!mem2[x].pq2.empty())
r = max(r, abs(p + mem2[x].pq2.top()));
x /= 2;
}
return r;
}
vector<pair<int, int>> can;
int ans[MAXN + 10];
int main()
{
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
scanf("%d%d%d", &n, &k, &q);
for(int i = 0; i < n; i++)
{
int x, t, a, b;
scanf("%d%d%d%d", &x, &t, &a, &b);
arr1.push_back({ a, x, t });
arr1.push_back({ b, x, -t });
}
for(int i = 0; i < q; i++)
{
int l, y;
scanf("%d%d", &l, &y);
arr2.push_back({ y, 2, l, i, -1 });
com.push_back(l);
}
sort(com.begin(), com.end());
com.erase(unique(com.begin(), com.end()), com.end());
for(bp = 1; bp < (int)com.size(); bp *= 2);
sort(arr1.begin(), arr1.end());
int cur, cnt = 0;
for(eve1 &e : arr1)
{
if(e.d > 0)
{
if(loc1[e.d].size() == 0)
{
cnt++;
if(cnt == k)
cur = e.t;
}
auto it = loc1[e.d].find(e.x);
if(it != loc1[e.d].end())
{
it->second.c++;
continue;
}
it = loc1[e.d].insert({ e.x, { 1, 1, e.t, INF, e.t } }).first;
ent1 &p = it->second;
if(it != loc1[e.d].begin())
{
int x = prev(it)->first;
ent1 &q = prev(it)->second;
add_seg(q.rt, e.t - 1, x, q.r);
q.rt = e.t;
q.r = (x + e.x) / 2;
p.l = (x + e.x + 1) / 2;
}
if(next(it) != loc1[e.d].end())
{
int x = next(it)->first;
ent1 &q = next(it)->second;
add_seg(q.lt, e.t - 1, x, q.l);
q.lt = e.t;
q.l = (x + e.x + 1) / 2;
p.r = (x + e.x) / 2;
}
}
else
{
e.d = -e.d;
auto it = loc1[e.d].find(e.x);
ent1 &p = it->second;
if(p.c > 1)
{
p.c--;
continue;
}
add_seg(p.lt, e.t, e.x, p.l);
add_seg(p.rt, e.t, e.x, p.r);
if(it != loc1[e.d].begin())
{
int x = prev(it)->first;
ent1 &q = prev(it)->second;
add_seg(q.rt, e.t, x, q.r);
q.rt = e.t + 1;
if(next(it) != loc1[e.d].end())
{
int y = next(it)->first;
q.r = (x + y) / 2;
}
else
q.r = INF;
}
if(next(it) != loc1[e.d].end())
{
int x = next(it)->first;
ent1 &q = next(it)->second;
add_seg(q.lt, e.t, x, q.l);
q.lt = e.t + 1;
if(it != loc1[e.d].begin())
{
int y = prev(it)->first;
q.l = (y + x + 1) / 2;
}
else
q.l = 1;
}
loc1[e.d].erase(it);
if(loc1[e.d].size() == 0)
{
if(cnt == k)
can.push_back({ cur, e.t });
cnt--;
}
}
}
sort(arr2.begin(), arr2.end());
int p = 0, sz = (int)can.size();
for(eve2 &e : arr2)
{
if(e.p == 1 || e.p == 3)
add_mem(e);
else
{
while(p < sz && can[p].second < e.t)
p++;
if(p < sz && can[p].first <= e.t)
ans[e.y] = get_mem(e.x);
else
ans[e.y] = -1;
}
}
for(int i = 0; i < q; i++)
printf("%d\n", ans[i]);
return 0;
}
