#include <stdio.h>
#include <sys/time.h>
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
#define N 300000
#define K 300000
#define Q 300000
#define M (300000 + 2)
#define M_ (1 << 19) /* M_ = pow2(ceil(log2(M))) */
#define T (K * 3 + N * 6)
#define INF 0x3f3f3f3f
unsigned int X;
void srand_() {
struct timeval tv;
gettimeofday(&tv, NULL);
X = tv.tv_sec ^ tv.tv_usec | 1;
}
int rand_() {
return (X *= 3) >> 1;
}
int *vv;
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h_ = hh[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = vv[hh[j]] - vv[h_];
if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}
int zz[T + 1], ll[T + 1], rr[T + 1], kk[T + 1], cnt[T + 1];
int node(int key) {
static int _ = 1;
zz[_] = rand_();
kk[_] = key;
return _++;
}
int l_, r_;
int i_;
void split_(int i, int key) {
if (i == 0) {
i_ = l_ = r_ = 0;
return;
}
if (kk[i] < key) {
split_(rr[i], key);
rr[i] = l_, l_ = i;
} else if (kk[i] > key) {
split_(ll[i], key);
ll[i] = r_, r_ = i;
} else {
i_ = i, l_ = ll[i], r_ = rr[i];
ll[i] = rr[i] = 0;
}
}
int merge(int i, int j) {
if (i == 0)
return j;
if (j == 0)
return i;
if (zz[i] < zz[j]) {
rr[i] = merge(rr[i], j);
return i;
} else {
ll[j] = merge(i, ll[j]);
return j;
}
}
void split(int i, int key) {
split_(i, key);
r_ = merge(i_, r_);
}
int first(int i) {
while (ll[i] != 0)
i = ll[i];
return i;
}
int last(int i) {
while (rr[i] != 0)
i = rr[i];
return i;
}
int add(int i, int key) {
split_(i, key);
if (i_ == 0)
i_ = node(key);
cnt[i_]++;
return merge(l_, merge(i_, r_));
}
int erase(int i, int key) {
split_(i, key);
if (--cnt[i_] == 0)
i_ = 0;
return merge(l_, merge(i_, r_));
}
int aa[M], m;
int ii(int a) {
int lower = 0, upper = m - 1;
while (lower < upper) {
int t = (lower + upper) / 2;
if (aa[t] < a)
lower = t + 1;
else if (aa[t] > a)
upper = t - 1;
else
lower = upper = t;
}
return lower;
}
int st[M_ * 2], mx[M_ * 2], m_;
void build(int *aa, int m) {
int i;
m_ = 1;
while (m_ < m)
m_ <<= 1;
for (i = 0; i < m_; i++) {
st[m_ + i] = INF;
mx[m_ + i] = i < m ? aa[i] : -INF;
}
for (i = m_ - 1; i > 0; i--) {
st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
mx[i] = max(mx[i << 1 | 0], mx[i << 1 | 1]);
}
}
void update(int i, int x) {
st[i += m_] = x;
while (i > 1) {
i >>= 1;
st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
}
}
int tr_[M];
void update_(int l, int r, int t) {
r = ii(r);
if (t == +1)
tr_[r] = add(tr_[r], l);
else
tr_[r] = erase(tr_[r], l);
update(r, tr_[r] == 0 ? INF : kk[first(tr_[r])]);
}
int query(int x) {
int i = 1, v = INF;
while (i < m_) {
if (x > mx[i << 1 | 0]) {
i = i << 1 | 1;
continue;
}
if (mx[i << 1 | 0] + 1 + min(st[i << 1 | 1], v) <= 2 * x)
i = i << 1 | 1;
else {
v = min(v, st[i << 1 | 1]);
i = i << 1 | 0;
}
}
return min(2 * x - min(v, st[i]), mx[i]) - x;
}
int main() {
static int xx[N], gg[N], ll[N], rr[N], yy[Q], tt[Q], ans[Q];
static int hh[M], hh0[N], hh1[N], hh2[Q];
static int tr[K], cnt_[K];
int n, k, q, i, i0, i1, i2, active;
srand_();
scanf("%d%d%d", &n, &k, &q);
for (i = 0; i < n; i++) {
scanf("%d%d%d%d", &xx[i], &gg[i], &ll[i], &rr[i]), gg[i]--;
hh[i] = i;
hh0[i] = i;
hh1[i] = i;
}
for (i = 0; i < q; i++) {
scanf("%d%d", &yy[i], &tt[i]);
hh2[i] = i;
}
vv = xx, sort(hh, 0, n);
vv = ll, sort(hh0, 0, n);
vv = rr, sort(hh1, 0, n);
vv = tt, sort(hh2, 0, q);
for (i = 0; i < k; i++) {
tr[i] = add(tr[i], -INF);
tr[i] = add(tr[i], +INF);
update_(-INF, +INF, +1);
}
m = 0;
aa[m++] = -INF;
for (i = 0; i < n; i++)
if (i == 0 || xx[hh[i]] != xx[hh[i - 1]])
aa[m++] = xx[hh[i]];
aa[m++] = +INF;
build(aa, m);
i0 = i1 = i2 = 0;
active = 0;
for (i = 0; i < q; i++) {
int h, g, x, l, r, prev, next;
while (i0 < n && ll[hh0[i0]] <= tt[hh2[i]]) {
h = hh0[i0], g = gg[h], x = xx[h];
split(tr[g], x);
l = l_, r = r_;
prev = last(l);
next = first(r);
update_(kk[prev], kk[next], -1);
update_(kk[prev], x, +1);
update_(x, kk[next], +1);
tr[g] = add(merge(l, r), x);
if (++cnt_[g] == 1)
active++;
i0++;
}
while (i1 < n && rr[hh1[i1]] < tt[hh2[i]]) {
h = hh1[i1], g = gg[h], x = xx[h];
tr[g] = erase(tr[g], x);
split(tr[g], x);
l = l_, r = r_;
prev = last(l);
next = first(r);
update_(kk[prev], kk[next], +1);
update_(kk[prev], x, -1);
update_(x, kk[next], -1);
tr[g] = merge(l, r);
if (--cnt_[g] == 0)
active--;
i1++;
}
ans[hh2[i]] = active == k ? query(yy[hh2[i]]) : -1;
}
for (i = 0; i < q; i++)
printf("%d\n", ans[i]);
return 0;
}
