题意：
题解：
完全想歪了。一开始一直在想把每种商店分开考虑，然而并不会做。。
事实上问题就是问最小要多大的区间才能包含所有颜色。我们可以先二分答案，当前答案$d$合法的条件就是$[x + d + 1, +\infty)$的前驱的最小值$\ge x - d$，这个用线段树维护就好。注意因为一个位置可能包含多个商店，所以每个点开一个可删堆或multiset维护。
然而这样是$log^2$的，而我的常数又超级大。。所以写了一个$log$的做法。具体来说就是把二分+线段树改成直接在线段树上二分，yy一下就出来了吧。
代码：
#include <bits/stdc++.h>
using namespace std;
char O[1<<14],*S=O,*T=O;
#define gc (S==T&&(T=(S=O)+fread(O,1,1<<14,stdin),S==T)?-1:*S++)
inline int read(){
int x=0,f=1; char ch=gc;
while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=gc;}
while(ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=gc;}
return x*f;
}
const int inf = 2147483647;
int n, k, q, nn = 0, num = 0, cnt = 0;
multiset<int> s[300010];
struct th
{
int x, type, t, p, ans;
} a[900010];
struct hp
{
priority_queue<int, vector<int>, greater<int> > a, b;
void insert(int x) { a.push(x); }
void erase(int x) { b.push(x); }
int top()
{
while (!b.empty() && b.top() == a.top()) a.pop(), b.pop();
return a.top();
}
bool empty() { return a.size() == b.size(); }
};
struct tree
{
int l, r, c;
tree *lc, *rc;
hp *s;
tree(int l, int r) : l(l), r(r), c(inf), lc(NULL), rc(NULL), s(NULL) {}
} *root;
int cmp(th x, th y)
{
return x.t == y.t ? x.type * x.p > y.type * y.p : x.t < y.t;
}
void chg(tree *i, int p, int o, int n)
{
if (i->l == i->r)
{
if (!i->s) i->s = new hp;
if (o != inf) i->s->erase(o);
if (n != inf) i->s->insert(n);
i->c = ((!i->s->empty()) ? (i->s->top()) : inf);
return;
}
int md = i->l + i->r >> 1;
if (p <= md)
{
if (!i->lc) i->lc = new tree(i->l, md);
chg(i->lc, p, o, n);
}
else
{
if (!i->rc) i->rc = new tree(md + 1, i->r);
chg(i->rc, p, o, n);
}
i->c = min(i->lc ? i->lc->c : inf, i->rc ? i->rc->c : inf);
}
int get(tree *i, int pos, int now)
{
if (i->l == i->r)
{
return i->l;
}
int md = i->l + i->r >> 1;
if (pos > md)
{
if (!i->rc) i->rc = new tree(md + 1, i->r);
return get(i->rc, pos, now);
}
int hh = min(now, i->rc ? i->rc->c : inf);
if (hh >= pos - (md - pos))
{
if (!i->lc) i->lc = new tree(i->l, md);
return get(i->lc, pos, hh);
}
else
{
if (!i->rc) i->rc = new tree(md + 1, i->r);
return get(i->rc, pos, now);
}
}
int cmpp(th x, th y)
{
return x.p < y.p;
}
int main()
{
n = read(), k = read(), q = read();
for (int i = 1; i <= n; i++)
{
int x, type, l, r;
x = read(), type = read(), l = read(), r = read();
a[++num] = {x, type, l, 1, 0};
a[++num] = {x, type, r, -1, 0};
}
for (int i = 1; i <= q; i++)
{
num++;
a[num].x = read(), a[num].t = read();
a[num].type = 0;
a[num].p = i;
}
sort(a + 1, a + 1 + num, cmp);
root = new tree(1, 1000000001);
for (int i = 1; i <= k; i++)
{
s[i].insert(1000000001);
chg(root, 1000000001, inf, -inf);
}
for (int i = 1; i <= num; i++)
{
if (a[i].type)
{
if (a[i].p == 1)
{
if (s[a[i].type].find(a[i].x) == s[a[i].type].end())
{
if (s[a[i].type].size() == 1) cnt++;
multiset<int>::iterator it = s[a[i].type].lower_bound(a[i].x);
if (it != s[a[i].type].begin())
{
multiset<int>::iterator pre = it;
pre--;
chg(root, *it, *pre, a[i].x);
chg(root, a[i].x, inf, *pre);
}
else
{
chg(root, *it, -inf, a[i].x);
chg(root, a[i].x, inf, -inf);
}
}
s[a[i].type].insert(a[i].x);
}
else
{
if (s[a[i].type].count(a[i].x) == 1)
{
multiset<int>::iterator it = s[a[i].type].find(a[i].x);
if (it != s[a[i].type].begin())
{
multiset<int>::iterator pre = it;
pre--;
chg(root, a[i].x, *pre, inf);
it++;
chg(root, *it, a[i].x, *pre);
}
else
{
chg(root, *it, -inf, inf);
chg(root, *++it, a[i].x, -inf);
}
}
s[a[i].type].erase(s[a[i].type].find(a[i].x));
if (s[a[i].type].size() == 1) cnt--;
}
}
else
{
if (cnt < k) a[i].ans = -1;
else
{
a[i].ans = get(root, a[i].x, inf) - a[i].x;
}
}
}
sort(a + 1, a + 1 + num, cmpp);
for (int i = 1; i <= num; i++)
if (a[i].type == 0)
printf("%d\n", ~a[i].ans ? a[i].ans : -1);
}