// Compile with: g++ -std=c++17 -O2 curtains_subtask5.cpp -o curtains
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using vi = vector<int>;
struct Node {
vector<pair<int,int>> intervals; // (l, r) sorted by r
vector<int> prefix_hole; // size = intervals.size(), hole values
vector<int> prefix_reach; // size = intervals.size(), reach values
};
struct SegTree {
int n;
vector<Node> st;
vector<vector<pair<int,int>>> start_at; // intervals starting at position i
SegTree(int _n=0){ init(_n); }
void init(int _n){
n = _n;
st.assign(4*n+5, Node());
start_at.assign(n+2, {});
}
void add_interval_input(int l, int r){
if(l<1 || l>n) return;
start_at[l].push_back({l,r});
}
// build: merge children intervals and compute prefix arrays per node
void build_all(int idx, int L, int R){
if(L==R){
auto &node = st[idx];
node.intervals = start_at[L];
sort(node.intervals.begin(), node.intervals.end(), [](auto &a, auto &b){
if(a.second != b.second) return a.second < b.second;
return a.first < b.first;
});
} else {
int mid=(L+R)/2;
build_all(idx*2, L, mid);
build_all(idx*2+1, mid+1, R);
// merge child intervals by r
auto &left = st[idx*2].intervals;
auto &right = st[idx*2+1].intervals;
auto &nodeint = st[idx].intervals;
nodeint.clear();
nodeint.reserve(left.size() + right.size());
std::merge(left.begin(), left.end(), right.begin(), right.end(),
back_inserter(nodeint),
[](const pair<int,int>&a, const pair<int,int>&b){
if(a.second != b.second) return a.second < b.second;
return a.first < b.first;
});
}
// compute prefix arrays for this node (DSU marks inside [L,R])
auto &node = st[idx];
int m = (int)node.intervals.size();
node.prefix_hole.assign(m, 0);
node.prefix_reach.assign(m, 0);
if(m == 0) return; // nothing to do
int len = R - L + 1;
// DSU parent: parent[i] = largest uncovered index <= i (1-based within [L,R])
vector<int> parent(len+1);
for(int i=0;i<=len;i++) parent[i] = i;
function<int(int)> findp = [&](int x)->int{
if(x<=0) return 0;
return parent[x]==x?x:parent[x]=findp(parent[x]);
};
int reach = R; // for empty prefix, reach = R (no extension beyond R)
for(int i=0;i<m;i++){
int l = node.intervals[i].first;
int r = node.intervals[i].second;
// update reach (furthest right covered by prefix)
reach = max(reach, r);
// mark covered positions inside [L,R]: cover [u,v]
int u = max(l, L);
int v = min(r, R);
if(u <= v){
int pos = findp(v - L + 1);
while(pos > 0 && (L + pos - 1) >= u){
// mark pos as covered
parent[pos] = pos - 1;
pos = findp(pos);
}
}
// compute hole: largest index inside [L,R] that is uncovered
int last_uncovered = findp(len); // index in 1..len or 0
int hole;
if(last_uncovered == 0) hole = L - 1; // no hole inside
else hole = L + last_uncovered - 1;
node.prefix_hole[i] = hole;
node.prefix_reach[i] = reach;
}
}
// collect nodes fully inside [ql,qr]
void collect_nodes(int idx, int L, int R, int ql, int qr, vector<tuple<int,int,int>> &out){
if(ql > R || qr < L) return;
if(ql <= L && R <= qr){
out.emplace_back(idx, L, R);
return;
}
int mid=(L+R)/2;
collect_nodes(idx*2, L, mid, ql, qr, out);
collect_nodes(idx*2+1, mid+1, R, ql, qr, out);
}
// combine two adjacent segments:
// left covers [a,b], right covers [b+1,c]
// left: (hole1, reach1), right: (hole2, reach2)
// hole values use sentinel: hole = interval.L - 1 means no hole in that interval
pair<int,int> combine_adjacent(const pair<int,int> &left, const pair<int,int> &right,
int a, int b, int c){
int hole1 = left.first, reach1 = left.second;
int hole2 = right.first, reach2 = right.second;
int hole, reach;
if(hole1 >= a){
// left has a hole inside [a,b] -> cannot be fixed by right
hole = hole1;
} else {
// left has no hole inside [a,b]
if(hole2 >= b+1){
// right has a hole in [b+1,c]; left can fix it only if reach1 >= hole2
if(reach1 >= hole2){
hole = a - 1; // fixed -> no hole
} else {
hole = hole2;
}
} else {
// right has no hole -> no hole overall
hole = a - 1;
}
}
reach = max(reach1, reach2);
return {hole, reach};
}
// query: returns true if [s,e] can be exactly covered
bool query(int s, int e){
vector<tuple<int,int,int>> segs;
collect_nodes(1,1,n,s,e,segs);
if(segs.empty()) return false;
// sort nodes left->right by their L
sort(segs.begin(), segs.end(), [](auto &A, auto &B){
return get<1>(A) < get<1>(B);
});
bool started = false;
pair<int,int> cur; int curL=0, curR=0;
for(auto &t : segs){
int idx = get<0>(t), L = get<1>(t), R = get<2>(t);
auto &node = st[idx];
// find count of curtains with r <= e (binary search)
int cnt = 0;
if(!node.intervals.empty()){
// node.intervals sorted by r
int lo = 0, hi = (int)node.intervals.size(); // count = first index with r > e
while(lo < hi){
int mid = (lo + hi) >> 1;
if(node.intervals[mid].second <= e) lo = mid + 1;
else hi = mid;
}
cnt = lo;
}
pair<int,int> nodeRes;
if(cnt == 0){
// empty prefix: hole = R (largest uncovered inside), reach = R (no extension)
nodeRes = { R, R };
} else {
nodeRes = { node.prefix_hole[cnt-1], node.prefix_reach[cnt-1] };
}
if(!started){
cur = nodeRes;
curL = L; curR = R;
started = true;
} else {
cur = combine_adjacent(cur, nodeRes, curL, curR, R);
curR = R;
}
}
// final check: if final hole < s then no hole inside [s,e]
int final_hole = cur.first;
return !(final_hole >= s && final_hole <= e);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#if 0
// Example I/O format (replace with your problem format)
// n m q
// m lines: l r
// q lines: s e
#endif
int n, m, q;
if(!(cin >> n >> m >> q)) return 0;
SegTree st(n);
for(int i=0;i<m;i++){
int l,r; cin>>l>>r;
if(l<1) l=1;
if(r>n) r=n;
if(l<=n && r>=1 && l<=r) st.add_interval_input(l,r);
}
st.build_all(1,1,n);
while(q--){
int s,e; cin >> s >> e;
if(s<1) s=1;
if(e>n) e=n;
if(s>e){
cout << "NO\n";
continue;
}
bool ok = st.query(s,e);
cout << (ok? "YES\n" : "NO\n");
}
return 0;
}
