#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};
// cout<<M<<" "<<A<<'\n';
// cout<<M<<" "<<B<<'\n';
dsuPar[j][A] = dsuPar[j][B] = M;
if (j == 0)
val[j][M] = max(val[j][A], val[j][B]);
else
val[j][M] = min(val[j][A], val[j][B]);
// val[j][M] = cr;
}
cur = 1;
dfs(j, M, 0);
// cout<<endl<<endl<<endl;
}
// for (int i=0;i<n;i++)
// cout<<crd[0][i]<<" "<<crd[1][i]<<'\n';
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];
// }
while (Par[0][A][0] != 0 and val[0][Par[0][A][0]] <= R[i])
A = Par[0][A][0];
while (Par[1][B][0] != 0 and val[1][Par[1][B][0]] >= L[i])
B = Par[1][B][0];
S[i] = A, E[i] = B;
Quer[Mx[0][A]].push_back(i);
// cout<<i<<" :: "<<Mn[0][A]<<" "<<Mx[0][A]<<" "<<Mn[1][B]<<" "<<Mx[1][B]<<'\n';
for (int k=1;k<=n;k++)
if ((Mn[0][A] <= crd[0][k]) & (crd[0][k] <= Mx[0][A]) & (Mn[1][B] <= crd[1][k]) & (crd[1][k] <= Mx[1][B]))
Ans[i] = 1;
}
// cout<<val[0][11]<<endl;
// cout<<val[1][11]<<endl;
// for (int i=0;i<n;i++)
// pnt.push_back({crd[0][i], crd[1][i]});
// sort(pnt.begin(), pnt.end());
// pnt.push_back({N, N});
// 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;
}
