//khodaya khodet komak kon
# include <bits/stdc++.h>
/*
// ordered_set
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
# define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 998244353;
const int base = 257;
int n, k, q, ans[xn], cnt[xn], ptr, ted;
int nxt[xn];
ppp a[xn];
pii b[xn];
vector <pip> query;
set <pii> st[xn];
void remove(int x){
-- cnt[x];
if (!cnt[x])
-- ted;
}
void add(int x){
if (!cnt[x])
++ ted;
++ cnt[x];
}
void solve(){
sort(a + 1, a + n + 1);
a[n + 1].A.A = inf;
for (int i = 1; i <= n; ++ i){
if (i)
remove(a[i - 1].A.B);
while (ptr <= n && ted < k)
add(a[ptr + 1].A.B);
nxt[i] = ptr;
}
nxt[0] = nxt[n + 1] = n + 1;
while (q --){
int x, y, ans = inf;
cin >> x >> y;
int l = 0, r = n + 1, mid;
while (r - l > 1){
mid = (l + r) / 2;
if (x - a[mid].A.A < a[nxt[mid]].A.A - x)
r = mid;
else
l = mid;
}
ans = min(ans, max(x - a[l].A.A, a[nxt[l]].A.A - x));
ans = min(ans, max(x - a[r].A.A, a[nxt[l]].A.A - x));
if (x > 1e8)
ans = - 1;
cout << ans << endl;
}
}
int main(){
InTheNameOfGod;
cin >> n >> k >> q;
for (int i = 1; i <= n; ++ i){
int x, t, l, r;
cin >> x >> t >> l >> r;
a[i] = {{x, t}, {l, r}};
query.push_back({l, {0, i}});
query.push_back({r, {2, i}});
}
if (n > 6e4){
solve();
return 0;
}
for (int i = 1; i <= q; ++ i){
int x, y;
cin >> x >> y;
b[i] = {x, y};
query.push_back({y, {1, i}});
}
for (int i = 1; i <= k; ++ i)
st[i].insert({inf, 0}), st[i].insert({- inf, 0});
sort(all(query));
for (pip Q : query){
int id = Q.B.B, t = Q.B.A;
if (t == 0)
st[a[id].A.B].insert({a[id].A.A, id});
else if (t == 2)
st[a[id].A.B].erase({a[id].A.A, id});
else{
int mx = 0;
for (int i = 1; i <= k; ++ i){
pii x = *st[i].lower_bound({b[id].A, 0});
pii y = *prev(st[i].lower_bound({b[id].A, 0}));
mx = max(mx, min(x.A - b[id].A, b[id].A - y.A));
}
if (mx > 1e8)
ans[id] = - 1;
else
ans[id] = mx;
}
}
for (int i = 1; i <= q; ++ i)
cout << ans[i] << endl;
return 0;
}
