#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 300001;
void checkmx(int& a, int b) { a = max(a,b); }
void checkmn(int& a, int b) { a = min(a,b); }
int getPos(vi& v, int x) { return ub(all(v),x)-v.begin()-1; }
template<int SZ> struct seg {
vector<array<int,4>> todo; // query minimum, interval min operations
vi num;
int mx[2][SZ];
void pull(int ind) {
F0R(i,2) mx[i][ind] = max(mx[i][2*ind],mx[i][2*ind+1]);
int t = min(mx[0][2*ind],mx[0][2*ind+1]);
if (t != mx[0][ind]) checkmx(t,mx[1][ind]);
}
void build(int ind, int L, int R) {
if (L == R) { mx[0][ind] = 2*MOD; mx[1][ind] = -2*MOD; return; }
int M = (L+R)/2;
build(2*ind,L,M); build(2*ind+1,M+1,R);
pull(ind);
}
void build() {
num.pb(-MOD);
for (auto a: todo) num.pb(a[2]), num.pb(a[3]+1);
sort(all(num)); num.erase(unique(all(num)),num.end());
build(1,0,sz(num)-1);
}
void push(int ind, int L, int R) {
if (L == R) return;
F0R(i,2) checkmn(mx[0][2*ind+i],mx[0][ind]);
}
void modify(int x, int y, int t, int ind, int L, int R) {
if (R < x || y < L || mx[0][ind] <= t) return;
push(ind,L,R);
if (x <= L && R <= y && mx[1][ind] < t) { mx[0][ind] = t; return; }
if (L == R) return;
int M = (L+R)/2;
modify(x,y,t,2*ind,L,M);
modify(x,y,t,2*ind+1,M+1,R);
pull(ind);
}
void modify(int x, int y, int t) {
// cout << "OOPS " << x << " " << y << " " << t << " " << getPos(num,x) << " " << getPos(num,y) << "\n";
modify(getPos(num,x),getPos(num,y),t,1,0,sz(num)-1);
}
int query(int x, int ind, int L, int R) {
push(ind,L,R);
if (L == R) return mx[0][ind];
int M = (L+R)/2;
if (x <= M) return query(x,2*ind,L,M);
return query(x,2*ind+1,M+1,R);
}
int query(int x) {
// cout << "HUH " << getPos(num,x) << "\n";
return query(getPos(num,x),1,0,sz(num)-1);
}
};
int n,k,q, ans[MX];
seg<1<<20> S[2];
map<pi,int> type[MX];
vector<array<int,5>> mod;
vector<array<int,3>> query;
ostream& operator <<(ostream& os, const pair<pi,int>& p) {
os << p.f.f << " " << p.f.s << " " << p.s << " | ";
return os;
}
void ins(int x, pair<pi,int> a, pair<pi,int> b) {
// cout << x << " | " << a << b << "\n";
if (a.f.f == -MOD && b.f.f == MOD) {
S[0].todo.pb({MOD,-MOD,a.s,x});
S[1].todo.pb({-MOD,MOD,a.s,x});
} else {
S[0].todo.pb({(a.f.f+b.f.f)/2,a.f.f,a.s,x}); // all x <= (a.f.f+b.f.f)/2
S[1].todo.pb({(a.f.f+b.f.f)/2+1,b.f.f,a.s,x});
}
}
pair<pi,int> getNex(auto& a, auto b) {
b = next(b);
if (b == a.end()) return {{MOD,-1},1};
return *b;
}
void init() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k >> q;
F0R(i,n) {
int x,t,a,b; cin >> x >> t >> a >> b;
mod.pb({a,1,t,x,i});
mod.pb({b+1,-1,t,x,i});
}
FOR(i,1,k+1) type[i][{-MOD,-1}] = 1;
sort(all(mod));
for (auto a: mod) {
pi t = {a[3],a[4]};
if (a[1] == 1) {
type[a[2]][t] = 0;
auto it = type[a[2]].find(t);
ins(a[0]-1,*prev(it),getNex(type[a[2]],it));
prev(it)->s = it->s = a[0];
} else {
auto it = type[a[2]].find(t);
ins(a[0]-1,*prev(it),*it);
ins(a[0]-1,*it,getNex(type[a[2]],it));
prev(it)->s = a[0];
type[a[2]].erase(it);
}
}
FOR(i,1,k+1) ins(1e8,*type[i].begin(),getNex(type[i],type[i].begin()));
}
void solve0() {
sort(query.rbegin(),query.rend());
S[0].build();
sort(all(S[0].todo));
for (auto a: query) {
while (sz(S[0].todo)) {
auto x = S[0].todo.back();
if (x[0] < a[0]) break;
S[0].modify(x[2],x[3],x[1]);
S[0].todo.pop_back();
}
checkmx(ans[a[2]],a[0]-S[0].query(a[1]));
}
}
void solve1() {
reverse(all(query));
S[1].build();
sort(all(S[1].todo)); reverse(all(S[1].todo));
for (auto a: query) {
while (sz(S[1].todo)) {
auto x = S[1].todo.back();
if (x[0] > a[0]) break;
S[1].modify(x[2],x[3],-x[1]);
S[1].todo.pop_back();
}
checkmx(ans[a[2]],-S[1].query(a[1])-a[0]);
}
}
int main() {
init();
F0R(i,q) {
int l,y; cin >> l >> y;
query.pb({l,y,i});
}
solve0();
solve1();
F0R(i,q) {
if (ans[i] > (1e8)) cout << -1;
else cout << ans[i];
cout << "\n";
}
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
Compilation message
new_home.cpp:132:21: error: use of 'auto' in parameter declaration only available with -std=c++14 or -std=gnu++14
pair<pi,int> getNex(auto& a, auto b) {
^~~~
new_home.cpp:132:30: error: use of 'auto' in parameter declaration only available with -std=c++14 or -std=gnu++14
pair<pi,int> getNex(auto& a, auto b) {
^~~~
new_home.cpp: In function 'std::pair<std::pair<int, int>, int> getNex(int&, int)':
new_home.cpp:133:15: error: no matching function for call to 'next(int&)'
b = next(b);
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from new_home.cpp:2:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note: candidate: template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
next(_ForwardIterator __x, typename
^~~~
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note: template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h: In substitution of 'template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type) [with _ForwardIterator = int]':
new_home.cpp:133:15: required from here
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: error: no type named 'difference_type' in 'struct std::iterator_traits<int>'
new_home.cpp:134:16: error: request for member 'end' in 'a', which is of non-class type 'int'
if (b == a.end()) return {{MOD,-1},1};
^~~
new_home.cpp:135:13: error: invalid type argument of unary '*' (have 'int')
return *b;
^
new_home.cpp: In function 'void init()':
new_home.cpp:153:47: error: invalid initialization of reference of type 'int&' from expression of type 'std::map<std::pair<int, int>, int>'
ins(a[0]-1,*prev(it),getNex(type[a[2]],it));
~~~~~~~~~^
new_home.cpp:132:14: note: in passing argument 1 of 'std::pair<std::pair<int, int>, int> getNex(int&, int)'
pair<pi,int> getNex(auto& a, auto b) {
^~~~~~
new_home.cpp:158:41: error: invalid initialization of reference of type 'int&' from expression of type 'std::map<std::pair<int, int>, int>'
ins(a[0]-1,*it,getNex(type[a[2]],it));
~~~~~~~~~^
new_home.cpp:132:14: note: in passing argument 1 of 'std::pair<std::pair<int, int>, int> getNex(int&, int)'
pair<pi,int> getNex(auto& a, auto b) {
^~~~~~
new_home.cpp:163:53: error: invalid initialization of reference of type 'int&' from expression of type 'std::map<std::pair<int, int>, int>'
FOR(i,1,k+1) ins(1e8,*type[i].begin(),getNex(type[i],type[i].begin()));
~~~~~~^
new_home.cpp:132:14: note: in passing argument 1 of 'std::pair<std::pair<int, int>, int> getNex(int&, int)'
pair<pi,int> getNex(auto& a, auto b) {
^~~~~~
