#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
// double rngesus_d(double l, double r){
// double cur = rngesus(0, MASK(60) - 1);
// cur /= MASK(60) - 1;
// return l + cur * (r - l);
// }
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
struct SegmentTree{
int n;
vector<multiset<int>> a;
vector<int> X;
SegmentTree(int _n, vector<int> _X){
n = _n;
a.resize(n * 4 + 4);
X = _X;
}
void add(int u, int v, int val, int l, int r, int id){
if (u <= l && r <= v){
a[id].insert(val);
return;
}
int mid = (l + r) >> 1;
if (u <= mid) add(u, v, val, l, mid, id * 2);
if (v > mid) add(u, v, val, mid + 1, r, id * 2 + 1);
}
void del(int u, int v, int val, int l, int r, int id){
if (u <= l && r <= v){
if (a[id].find(val) == a[id].end()) assert(false);
a[id].erase(a[id].find(val));
return;
}
int mid = (l + r) >> 1;
if (u <= mid) del(u, v, val, l, mid, id * 2);
if (v > mid) del(u, v, val, mid + 1, r, id * 2 + 1);
}
void add(int u, int v, int val){
u = lower_bound(ALL(X), u) - X.begin();
v = upper_bound(ALL(X), v) - X.begin() - 1;
if (u > v) return;
add(u, v, val, 1, n, 1);
}
void del(int u, int v, int val){
u = lower_bound(ALL(X), u) - X.begin();
v = upper_bound(ALL(X), v) - X.begin() - 1;
if (u > v) return;
del(u, v, val, 1, n, 1);
}
int get(int i, int vcl, int l, int r, int id){
int val = 0;
if (a[id].size()){
int j = *a[id].begin();
maximize(val, abs(j - vcl));
j = *a[id].rbegin();
maximize(val, abs(j - vcl));
}
if (l == r) return val;
int mid = (l + r) >> 1;
if (i <= mid) return max(val, get(i, vcl, l, mid, id * 2));
else return max(val, get(i, vcl, mid+1, r, id * 2 + 1));
}
int get(int i){
int idx = lower_bound(ALL(X), i) - X.begin();
return get(idx, i, 1, n, 1);
}
};
const int N = 3e5 + 69, INF = 1e9 + 69;
vector<int> X, T;
vector<int> coin_slot[N];
vector<int> enter_home[N], exit_home[N];
int ans[N];
multiset<int> S[N];
void add(int type, int pos, SegmentTree &st){
if (S[type].find(pos) != S[type].end()) {
S[type].insert(pos);
return;
}
int l = -1, r = -1;
auto it = S[type].lower_bound(pos);
if (it != S[type].end()){
r = *it;
}
if (it != S[type].begin()){
it--;
l = *it;
}
if (l != -1 || r != -1) {
if (l == -1){
st.del(1, r, r);
}
else if (r == -1){
st.del(l, INF, l);
}
else{
int mid = (l + r) >> 1;
st.del(l, mid, l);
st.del(mid+1, r, r);
}
}
if (l == -1){
st.add(1, pos, pos);
}
else{
int mid = (l + pos) >> 1;
st.add(l, mid, l);
st.add(mid+1, pos, pos);
}
if (r == -1){
st.add(pos, INF, pos);
}
else{
int mid = (pos + r) >> 1;
st.add(pos, mid, pos);
st.add(mid+1, r, r);
}
S[type].insert(pos);
}
void del(int type, int pos, SegmentTree &st){
S[type].erase(S[type].find(pos));
if (S[type].find(pos) != S[type].end()) {
return;
}
int l = -1, r = -1;
auto it = S[type].lower_bound(pos);
if (it != S[type].end()){
r = *it;
}
if (it != S[type].begin()){
it--;
l = *it;
}
if (l != -1 || r != -1) { // destroy existing bond
if (l == -1){
st.add(1, r, r);
}
else if (r == -1){
st.add(l, INF, l);
}
else{
int mid = (l + r) >> 1;
st.add(l, mid, l);
st.add(mid+1, r, r);
}
}
if (l == -1){
st.del(1, pos, pos);
}
else{
int mid = (l + pos) >> 1;
st.del(l, mid, l);
st.del(mid+1, pos, pos);
}
if (r == -1){
st.del(pos, INF, pos);
}
else{
int mid = (pos + r) >> 1;
st.del(pos, mid, pos);
st.del(mid+1, r, r);
}
}
void solve(){
int n, k, q; cin >> n >> k >> q;
vector<array<int, 4>> homes(n);
for(int i= 0; i < n; ++i) {
for(int j = 0; j < 4; ++j) cin >> homes[i][j];
}
vector<pair<int,int>> queries(q);
for(int i = 0; i < q; ++i) cin >> queries[i].first >> queries[i].second;
X.push_back(0); T.push_back(0);
for(auto i: queries){
X.push_back(i.first);
T.push_back(i.second);
}
remove_dup(X); remove_dup(T);
for(int i = 0; i < q; ++i){
int t = lower_bound(ALL(T), queries[i].second) - T.begin();
coin_slot[t].push_back(i);
}
for(int i = 0; i < n; ++i){
int l = lower_bound(ALL(T), homes[i][2]) - T.begin();
int r = upper_bound(ALL(T), homes[i][3]) - T.begin() - 1;
if (l > r) continue;
enter_home[l].push_back(i);
exit_home[r].push_back(i);
}
int cnt = 0;
int m = X.size() - 1;
SegmentTree st(m, X);
for(int it = 1; it < (int)T.size(); ++it){
for(int i: enter_home[it]){
int pos = homes[i][0], type = homes[i][1];
if (S[type].empty()) cnt++;
add(type, pos, st);
}
for(int i: coin_slot[it]){
if (cnt < k) ans[i] = -1;
else{
ans[i] = st.get(queries[i].first);
}
}
for(int i: exit_home[it]){
int pos = homes[i][0], type = homes[i][1];
del(type, pos, st);
if (S[type].empty()) cnt--;
}
}
for(int i = 0; i < q; ++i) cout << ans[i] << "\n";
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
clock_t start = clock();
solve();
cerr << "Time elapsed: " << clock() - start << "ms!\n";
return 0;
}
