#include<bits/stdc++.h>
using namespace std;
int N, K, Q, timeCount, xCount, x[300009], type[300009], a[300009], b[300009], location[300009], when[300009], ans[300009], realX[300009];
const int INF = 5e8;
int changesLine = 0;
vector < pair < int*, int > > changes[40];
multiset < int > S[300009];
vector < pair < int, int > > setChanges[40];
void update (int &x, int y)
{
if (y > x)
changes[changesLine].push_back ({&x, x}),
x = y;
}
int emptySets = 0;
void rollBack (int id)
{
reverse (changes[id].begin (), changes[id].end ());
for (auto it : changes[id])
*it.first = it.second;
changes[id].clear ();
for (auto it : setChanges[id])
emptySets -= S[it.first].empty (),
S[it.first].insert (it.second);
setChanges[id].clear ();
}
const int maxSize = 300009;
int aib[2][maxSize];
void update (int lin, int pos, int val)
{
while (pos <= xCount)
update (aib[lin][pos], val),
pos += pos - (pos & (pos - 1));
}
int query (int lin, int pos)
{
int ans = -INF;
while (pos)
ans = max (ans, aib[lin][pos]),
pos &= pos - 1;
return ans;
}
int firstBigger (int val)
{
int p = 1, u = xCount, mij, ras = xCount + 1;
while (p <= u)
{
mij = (p + u) >> 1;
if (realX[mij] > val) ras = mij, u = mij - 1;
else p = mij + 1;
}
return ras;
}
int lastSmaller (int val)
{
int p = 1, u = xCount, mij, ras = 0;
while (p <= u)
{
mij = (p + u) >> 1;
if (realX[mij] < val) ras = mij, p = mij + 1;
else u = mij - 1;
}
return ras;
}
int maxDist (int x)
{
int v1 = query (0, xCount - x + 1) + realX[x];
int v2 = query (1, x) - realX[x];
return max (v1, v2);
}
void addSegm (int x0, int x2)
{
int mid = (x0 + x2) / 2, pos = lastSmaller (mid + 1);
if (pos >= 1) update (0, xCount - pos + 1, -x0);
if (pos < xCount) update (1, pos + 1, x2);
}
void delPoint (int type, int x)
{
auto it = S[type].lower_bound (x), it0 = it, it2 = it;
int x0, x2;
if (it0 == S[type].begin ()) x0 = -INF;
else it0 --, x0 = *it0;
it2 ++;
if (it2 == S[type].end ()) x2 = +INF;
else x2 = *it2;
if (x0 != x && x2 != x)
addSegm (x0, x2);
setChanges[changesLine].push_back ({type, x});
S[type].erase (it), emptySets += S[type].empty ();
}
void init ()
{
for (int i=1; i<=N; i++)
if (a[i] <= b[i])
S[type[i]].insert (x[i]);
for (int i=1; i<=xCount; i++)
aib[0][i] = aib[1][i] = -INF;
for (int i=1; i<=K; i++)
{
emptySets += S[i].empty ();
int lastX = -INF;
for (auto it : S[i])
addSegm (lastX, it),
lastX = it;
addSegm (lastX, +INF);
}
changes[changesLine].clear ();
}
int mpX[300009];
vector < int > normT;
void normalize ()
{
sort (normT.begin (), normT.end ());
normT.erase (unique (normT.begin (), normT.end ()), normT.end ());
timeCount = normT.size ();
sort (mpX + 1, mpX + Q + 1);
for (int i=1; i<=Q; i++)
if (i == 1 || mpX[i] != mpX[i - 1])
realX[++xCount] = mpX[i];
for (int i=1; i<=Q; i++)
{
int p = 1, u = timeCount, mij, ras = 0;
while (p <= u)
{
mij = (p + u) >> 1;
if (normT[mij - 1] <= when[i]) ras = mij, p = mij + 1;
else u = mij - 1;
}
when[i] = ras;
location[i] = lastSmaller (location[i] + 1);
}
for (int i=1; i<=N; i++)
{
int p = 1, u = timeCount, mij, ras = timeCount + 1;
while (p <= u)
{
mij = (p + u) >> 1;
if (normT[mij - 1] >= a[i]) ras = mij, u = mij - 1;
else p = mij + 1;
}
a[i] = ras, ras = 0, p = 1, u = timeCount;
while (p <= u)
{
mij = (p + u) >> 1;
if (normT[mij - 1] <= b[i]) ras = mij, p = mij + 1;
else u = mij - 1;
}
b[i] = ras;
}
}
vector < int > qry[300009];
void solveDC (int nod, int st, int dr, vector < int > &A, vector < int > &B)
{
changesLine ++;
int mij = (st + dr) >> 1;
for (auto it : A)
if (a[it] > dr)
delPoint (type[it], x[it]);
for (auto it : B)
if (b[it] < st)
delPoint (type[it], x[it]);
if (st == dr)
{
for (auto it : qry[st])
if (emptySets > 0) ans[it] = -1;
else ans[it] = maxDist (location[it]);
}
else
{
vector < int > leftA, leftB, rightA, rightB;
for (auto it : A)
if (a[it] <= dr)
{
leftA.push_back (it);
if (a[it] - 1 > mij) rightA.push_back (it);
}
for (auto it : B)
if (b[it] >= st)
{
rightB.push_back (it);
if (b[it] + 1 <= mij) leftB.push_back (it);
}
int f1 = nod << 1, f2 = f1 | 1;
solveDC (f1, st, mij, leftA, leftB);
solveDC (f2, mij + 1, dr, rightA, rightB);
}
rollBack (changesLine), changesLine --;
}
void Read (int &x);
int main ()
{
//freopen ("100", "r", stdin);
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
Read (N), Read (K), Read (Q), normT.resize (Q);
for (int i=1; i<=N; i++)
Read (x[i]), Read (type[i]), Read (a[i]), Read (b[i]);
for (int i=1; i<=Q; i++)
Read (location[i]), Read (when[i]),
normT[i - 1] = when[i], mpX[i] = location[i];
normalize ();
init ();
vector < int > initA, initB;
for (int i=1; i<=N; i++)
if (a[i] <= b[i])
initA.push_back (i),
initB.push_back (i);
for (int i=1; i<=Q; i++)
qry[when[i]].push_back (i);
solveDC (1, 1, timeCount, initA, initB);
for (int i=1; i<=Q; i++)
printf ("%d\n", ans[i]);
return 0;
}
const int maxl = 500000;
int pos = maxl - 1;
char buff[maxl];
void Next ()
{
if (++pos == maxl)
fread (buff, 1, maxl, stdin), pos = 0;
}
void Read (int &x)
{
while (buff[pos] < '0' || buff[pos] > '9') Next ();
for (x = 0; buff[pos] >= '0' && buff[pos] <= '9'; Next ()) x = x * 10 + buff[pos] - '0';
}
