#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];
void create(int x, int type, int l, int r, int x1, int x2, int v, int y) {
if(x2 < l or r < x1)
return;
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;
}
int m = (l + r) >> 1;
create(x + x, type, l, m, x1, x2, v, y);
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();
}
void 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) {
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);
}
}
}
else {
int m = (l + r) >> 1;
solve(x + x, l, m);
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();
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;
}
