#pragma GCC optimize("arch=skylake")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
const int INF = 1e9+5;
vector<pair<int, pair<int, int>>> ev;
vector<int> cp, cpy;
int n, q, k;
int ans[maxn];
int p[maxn], ty[maxn];
int L[maxn], Y[maxn];
int st[4*maxn][2];
struct ev_upd{
int l, r, val, ty;
ev_upd(int _l, int _r, int _val, int _ty): l(_l), r(_r), val(_val), ty(_ty){};
bool operator<(const ev_upd &b)const {
return tie(l, r, val, ty) < tie(b.l, b.r, b.val, b.ty);
}
};
map<ev_upd, vector<int>> mp;
map<int, vector<pair<int, int>>> leaf_q;
multiset<int> pos[maxn];
vector<ev_upd> st_time[4*maxn];
int crrt;
pair<pair<int, int>, int> undo_stack[maxn*20];
int stksz = 0;
// 0 is min, 1 is max
void upd_st(const ev_upd &ele, int &cnt, int l = 0, int r = cp.size()-1, int id = 1){
if(ele.l > cp[r] || ele.r < cp[l])return;
if(ele.l <= cp[l] && cp[r] <= ele.r){
if(ele.ty == 0){
if(st[id][0] > ele.val){
undo_stack[stksz++] = make_pair(make_pair(id, 0), st[id][0]);
st[id][0] = ele.val;
cnt++;
}
}
else {
if(st[id][1] < ele.val){
undo_stack[stksz++] = make_pair(make_pair(id, 1), st[id][1]);
st[id][1] = ele.val;
cnt++;
}
}
}
else {
int mid = (l+r)>>1;
upd_st(ele, cnt, l, mid, id<<1);
upd_st(ele, cnt, mid+1, r, id<<1|1);
}
}
int query_st(int pos, int l = 0, int r = cp.size()-1, int id = 1){
int re = max(st[id][1] - pos, pos - st[id][0]);
if(l < r){
int mid = (l + r)>>1;
if(pos <= cp[mid])re = max(re, query_st(pos, l, mid, id<<1));
else re = max(re, query_st(pos, mid+1, r, id<<1|1));
}
return re;
}
void time_add(int ql, int qr, const ev_upd &ele, int l = 0, int r = cpy.size()-1, int id = 1){
if(ql > qr || ql > cpy[r] || qr < cpy[l])return;
if(ql <= cpy[l] && cpy[r] <= qr)st_time[id].push_back(ele);
else {
int mid = (l+r)>>1;
time_add(ql, qr, ele, l, mid, id<<1);
time_add(ql, qr, ele, mid+1, r, id<<1|1);
}
}
int sumcol[maxn];
int sumall = 0, ptr = 0;
void time_dfs(int l = 0, int r = cpy.size()-1, int id = 1){
int cnt = 0;
for(auto ele: st_time[id]) {
upd_st(ele, cnt);
}
if(l == r){
while(ptr < ev.size() && ev[ptr].first <= cpy[l]){
if(ev[ptr].second.first){
sumcol[ty[ev[ptr].second.second]]--;
if(!sumcol[ty[ev[ptr].second.second]])sumall--;
}
else {
if(!sumcol[ty[ev[ptr].second.second]])sumall++;
sumcol[ty[ev[ptr].second.second]]++;
}
ptr++;
}
// cout << sumall << endl;
for(auto qq: leaf_q[cpy[l]]){
ans[qq.second] = sumall < k ? -1 : query_st(qq.first);
}
}
else {
int mid = (l+r)>>1;
time_dfs(l, mid, id<<1);
time_dfs(mid+1, r, id<<1|1);
}
for(int i = 0; i < cnt; i++){
stksz--;
st[undo_stack[stksz].first.first][undo_stack[stksz].first.second] = undo_stack[stksz].second;
}
}
void add_st(int l, int r, int val, int ty){
if(l > r)return;
mp[ev_upd(l, r, val, ty)].push_back(crrt);
}
void del_st(int l, int r, int val, int ty){
if(l > r)return;
ev_upd ele(l, r, val, ty);
time_add(mp[ele].back(), crrt - 1, ele);
mp[ele].pop_back();
}
void add_range(int l, int r){
if(l == -INF)add_st(-INF, r, r, 1);
else if(r == INF)add_st(l+1, INF, l, 0);
else {
int mid = (l+r)/2;
add_st(l+1, mid, l, 0);
add_st(mid+1, r, r, 1);
}
}
void del_range(int l, int r){
if(l == -INF)del_st(-INF, r, r, 1);
else if(r == INF)del_st(l+1, INF, l, 0);
else {
int mid = (l+r)/2;
del_st(l+1, mid, l, 0);
del_st(mid+1, r, r, 1);
}
}
void add(int x, int col){
auto it = pos[col].insert(x);
if(pos[col].size() == 1){
add_range(-INF, x);
add_range(x, INF);
}
else {
if(next(it) == pos[col].end()){
del_range(*prev(it), INF);
add_range(*prev(it), x);
add_range(x, INF);
}
else if(it == pos[col].begin()){
del_range(-INF, *next(it));
add_range(-INF, x);
add_range(x, *next(it));
}
else {
del_range(*prev(it), *next(it));
add_range(*prev(it), *it);
add_range(*it, *next(it));
}
}
}
void del(int x, int col){
auto it = pos[col].erase(pos[col].find(x));
if(pos[col].size() == 0){
del_range(-INF, x);
del_range(x, INF);
}
else {
if(it == pos[col].end()){
del_range(x, INF);
del_range(*prev(it), x);
add_range(*prev(it), INF);
}
else if(it == pos[col].begin()){
del_range(-INF, x);
del_range(x, *it);
add_range(-INF, *it);
}
else {
del_range(x, *it);
del_range(*prev(it), x);
add_range(*prev(it), *it);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> q;
for(int i = 0; i < 4*maxn; i++)st[i][0] = INF, st[i][1] = -INF;
for(int i = 1; i <= n; i++){
int a, b;
cin >> p[i] >> ty[i] >> a >> b;
ev.push_back({a, {0, i}});
ev.push_back({b+1, {1, i}});
}
for(int i = 1; i <= q; i++){
cin >> L[i] >> Y[i];
cp.push_back(L[i]);
cpy.push_back(Y[i]);
leaf_q[Y[i]].push_back({L[i], i});
}
sort(cp.begin(), cp.end());
cp.erase(unique(cp.begin(), cp.end()), cp.end());
sort(cpy.begin(), cpy.end());
cpy.erase(unique(cpy.begin(), cpy.end()), cpy.end());
sort(ev.begin(), ev.end());
for(auto v: ev){
crrt = v.first;
if(v.second.first)del(p[v.second.second], ty[v.second.second]);
else add(p[v.second.second], ty[v.second.second]);
}
time_dfs();
for(int i = 1; i <= q; i++)cout << ans[i] << "\n";
}
