#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 3e5 + 5;
const int OUT = 0, QUE = 1;
const int addPositive = 0, addNegative = 1;
int n, q, k, total;
int ans[N];
map<int, int> s[N];
int z, g;
int tree[2][N << 1];
int curX;
vector<pair<int, pair<int *, int>>> changes;
void update(int t, int l, int r, int x) {
for (l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
if ((l & 1) and x > tree[t][l]) {
changes.push_back({curX, {&tree[t][l], tree[t][l]}});
tree[t][l] = x;
}
if ((~r & 1) and x > tree[t][r]) {
changes.push_back({curX, {&tree[t][r], tree[t][r]}});
tree[t][r] = x;
}
}
}
int get(int t, int x) {
int res = -1e9;
x += N;
while (x >= 1) {
res = max(res, tree[t][x]);
x >>= 1;
}
return res;
}
inline int read() {
char c = getchar();
int x = 0;
while (c < '0' or c > '9')
c = getchar();
while ('0' <= c and c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
vector<pair<ii, int>> M[N * 4];
int isany[N * 4];
bool create(int x, int type, int l, int r, int x1, int x2, int v, int y) {
if (x2 < l or r < x1)
return false;
if (type == QUE)
isany[x] = 1;
if (x1 <= l and r <= x2) {
// printf("type = %d l = %d r = %d\n", type, l, r);
M[x].push_back({{type, v}, y});
return type == OUT;
}
int m = (l + r) >> 1;
if (create(x + x, type, l, m, x1, x2, v, y)) {
return true;
}
return create(x + x + 1, type, m + 1, r, x1, x2, v, y);
}
vector<int> ques;
int rid(int x) {
return lower_bound(ques.begin(), ques.end(), x) - ques.begin() + 1;
}
int lid(int x) {
return upper_bound(ques.begin(), ques.end(), x) - ques.begin();
}
vector<int> ins;
int ri(int x) {
return lower_bound(ins.begin(), ins.end(), x) - ins.begin() + 1;
}
int li(int x) {
return upper_bound(ins.begin(), ins.end(), x) - ins.begin();
}
bool solve(int x, int l, int r) {
// if(!isany[x])
// return;
int delTotal = 0;
curX = x;
bool HARD_FAIL = 0;
for (auto tmp : M[x]) {
int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
if (type == OUT) {
if (--s[t][x])
continue;
s[t].erase(x);
// printf("deleting location = %d type = %d\n", x, t);
auto it = s[t].begin();
int nxt = (it = s[t].upper_bound(x)) == s[t].end() ? -1 : it->first;
int bef = (it = s[t].lower_bound(x)) == s[t].begin() ? -1 : (--it)->first;
if (bef == -1 and nxt == -1) {
HARD_FAIL = 1;
} else if (bef == -1) {
update(addNegative, 1, lid((x + nxt) / 2), nxt);
} else if (nxt == -1) {
update(addPositive, rid((bef + x) / 2 + 1), z, -bef);
} else {
update(addPositive, rid((bef + x) / 2 + 1), lid((bef + nxt) / 2), -bef);
update(addNegative, rid((bef + nxt) / 2 + 1), lid((x + nxt) / 2), nxt);
}
}
}
if (HARD_FAIL) {
return true;
}
// if(HARD_FAIL) {
// for(auto tmp : M[x]) {
// int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
// if(type == OUT) {
// // printf("reverting x = %d t = %d\n", x, t);
// s[t][x]++;
// }
// }
// while(!changes.empty() and changes.back().first == x) {
// *changes.back().second.first = changes.back().second.second;
// changes.pop_back();
// }
// return;
// }
if (l == r) {
for (auto tmp : M[x]) {
int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
if (type == QUE) {
int a = get(0, rid(x));
int b = get(1, rid(x));
// printf("que x = %d i = %d a = %d b = %d\n", x, t, a, b);
ans[t] = max(a + x, b - x);
}
}
return false;
}
int m = (l + r) >> 1;
if (solve(x + x, l, m)) {
return true;
}
return solve(x + x + 1, m + 1, r);
// for(auto tmp : M[x]) {
// int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
// if(type == OUT) {
// // printf("reverting x = %d t = %d\n", x, t);
// s[t][x]++;
// }
// }
// while(!changes.empty() and changes.back().first == x) {
// *changes.back().second.first = changes.back().second.second;
// changes.pop_back();
// }
}
int x1[N], t1[N], a1[N], b1[N], x2[N], y2[N];
int main() {
n = read();
k = read();
q = read();
for (int i = 1; i <= n; i++) {
int x, t, a, b;
x = read();
t = read();
a = read();
b = read();
assert(a == 1);
x1[i] = x, t1[i] = t, a1[i] = a, b1[i] = b;
}
for (int i = 1; i <= q; i++) {
int x, y;
x = read();
y = read();
x2[i] = x;
y2[i] = y;
ins.push_back(y);
ques.push_back(x);
}
sort(ques.begin(), ques.end());
ques.resize(unique(ques.begin(), ques.end()) - ques.begin());
z = ques.size();
ins.push_back(0);
ins.push_back(1e8 + 1);
sort(ins.begin(), ins.end());
ins.resize(unique(ins.begin(), ins.end()) - ins.begin());
g = ins.size();
for (int i = 1; i <= n; i++) {
int x = x1[i], t = t1[i], a = a1[i], b = b1[i];
s[t][x]++;
a = li(a - 1);
b = ri(b + 1);
if (a != 1) {
create(1, OUT, 1, g, 1, a, x, t);
}
if (b != g) {
create(1, OUT, 1, g, b, g, x, t);
}
}
for (int i = 1; i <= q; i++) {
int x = x2[i], y = y2[i];
ans[i] = -1;
create(1, QUE, 1, g, ri(y), ri(y), x, i);
}
memset(tree, -63, sizeof(tree));
for (int i = 1; i <= k; i++) {
vector<int> v;
for (auto x : s[i])
v.push_back(x.first);
if (v.empty())
break;
total++;
update(addNegative, 1, rid(v[0]), v[0]);
for (int it = 0; it + 1 < v.size(); it++) {
update(addPositive, rid(v[it]), lid((v[it] + v[it + 1]) / 2), -v[it]);
update(addNegative, rid((v[it] + v[it + 1]) / 2 + 1), lid(v[it + 1]), v[it + 1]);
}
update(addPositive, rid(v.back()), z, -v.back());
}
changes.clear();
if (total == k)
solve(1, 1, g);
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}
