#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = (1<<18) + 1, K = N<<1;
int seg[K], Mn[2][K], Mx[2][K], val[2][K], Par[2][K][20], crd[2][K], dsuPar[2][K];
pair<int, int> Nei[2][K];
vector<int> Quer[K];
int cur, M, it;
void dfs(int t, int u, int p){
Par[t][u][0] = p;
for (int i=0;i<18;i++)
Par[t][u][i+1] = Par[t][Par[t][u][i]][i];
if (Nei[t][u].first == 0){
Mn[t][u] = Mx[t][u] = crd[t][u] = cur++;
return;
}
auto [lc, rc] = Nei[t][u];
dfs(t, lc, u);
dfs(t, rc, u);
Mn[t][u] = Mn[t][lc];
Mx[t][u] = Mx[t][rc];
}
void Update(int i, int vl, int cur = 1, int st = 1, int en = N){
if (i >= en or i < st)
return;
seg[cur] = vl;
if (en - st == 1)
return;
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Update(i, vl, lc, st, mid);
Update(i, vl, rc, mid, en);
}
int get(int l, int r, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return 0;
if (l <= st and r >= en)
return seg[cur];
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en));
}
int root(int t, int v){
return (dsuPar[t][v] == 0 ? v : dsuPar[t][v] = root(t, dsuPar[t][v]));
}
vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
vector<pair<int, int>> Edg[2], pnt;
vector<int> Ans((int)S.size(), 0);
for (int i=0;i<U.size();i++)
U[i]++, V[i]++;
for (int i=0;i<S.size();i++)
S[i]++, E[i]++, L[i]++, R[i]++;
for (int i=0;i<U.size();i++){
Edg[0].push_back({max(U[i], V[i]), i});
Edg[1].push_back({min(U[i], V[i]), i});
}
for (int i=1;i<=n;i++)
val[0][i] = val[1][i] = i;
sort(Edg[0].begin(), Edg[0].end());
sort(Edg[1].rbegin(), Edg[1].rend());
for (int j : {0, 1}){
M = n;
for (auto [cr, id] : Edg[j]){
int A = root(j, U[id]), B = root(j, V[id]);
if (A == B)
continue;
++M;
Nei[j][M] = {A, B};
dsuPar[j][A] = dsuPar[j][B] = M;
val[j][M] = cr;
}
cur = 1;
dfs(j, M, 0);
}
for (int i=0;i<S.size();i++){
swap(S[i], E[i]);
int A = S[i], B = E[i];
for (int j=18;j>=0;j--){
if (Par[0][A][j] != 0 and val[0][Par[0][A][j]] <= R[i])
A = Par[0][A][j];
if (Par[1][B][j] != 0 and val[1][Par[1][B][j]] >= L[i])
B = Par[1][B][j];
}
S[i] = A, E[i] = B;
Quer[Mx[0][A]].push_back(i);
}
for (int i=1;i<=n;i++)
pnt.push_back({crd[0][i], crd[1][i]});
sort(pnt.begin(), pnt.end());
for (auto [x, y] : pnt){
Update(y, x);
for (; it <= x; it++){
for (int id : Quer[it])
if (get(Mn[1][E[id]], Mx[1][E[id]] + 1) >= Mn[0][S[id]])
Ans[id] = 1;
}
}
return Ans;
}
