#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int dN = 4e5 + 5;
const int oN = 1600005;
const int M = 4e5 + 5;
vector<int> g[2][dN], s[oN];
int X[M], Y[M], id[M];
int p[2][dN], W[2][dN];
int up[2][dN][18], d[2][dN];
int tin[2][dN], tout[2][dN], arr[2][dN], ti[2];
int n, L1, R1, L2, R2;
bool cmp0(int i, int j){ return min(X[i], Y[i]) > min(X[j], Y[j]); }
bool cmp1(int i, int j){ return max(X[i], Y[i]) < max(X[j], Y[j]); }
int fp(int x, int u){
return u == p[x][u] ? u : p[x][u] = fp(x, p[x][u]);
}
int kth(int x, int u, int k){
for(int j = 17; j >= 0; --j)
if(k & (1 << j))
u = up[x][u][j];
return u;
}
void dfs(int x, int u, int par){
up[x][u][0] = par;
tin[x][u] = ti[x]++;
if(u != par) d[x][u] = d[x][par] + 1;
for(int j = 1; j < 18; ++j)
up[x][u][j] = up[x][ up[x][u][j-1] ][j-1];
for(int v : g[x][u])
dfs(x, v, u);
tout[x][u] = ti[x] - 1;
}
void bld(int ind, int l, int r){
if(l == r){
if(arr[0][l] != -1)
s[ind] = {arr[0][l]}; // FIX: no -1
return;
}
int m = (l + r) >> 1;
bld(ind<<1, l, m);
bld(ind<<1|1, m+1, r);
merge(s[ind<<1].begin(), s[ind<<1].end(),
s[ind<<1|1].begin(), s[ind<<1|1].end(),
back_inserter(s[ind]));
}
int qry(int ind, int l, int r){
if(l > R1 || r < L1) return 0;
if(L1 <= l && r <= R1){
return upper_bound(s[ind].begin(), s[ind].end(), R2)
- lower_bound(s[ind].begin(), s[ind].end(), L2);
}
int m = (l + r) >> 1;
return qry(ind<<1, l, m) + qry(ind<<1|1, m+1, r);
}
vector<int> check_validity(
int _n,
vector<int> XX,
vector<int> YY,
vector<int> S,
vector<int> E,
vector<int> L,
vector<int> R
){
int m = XX.size();
n = _n;
for(int i = 0; i < m; ++i){
X[i] = XX[i];
Y[i] = YY[i];
id[i] = i;
}
for(int x = 0; x < 2; ++x)
for(int i = 0; i < 2*n; ++i)
p[x][i] = i;
int nn[2] = {n, n};
for(int x = 0; x < 2; ++x){
if(x == 0) sort(id, id+m, cmp0);
else sort(id, id+m, cmp1);
for(int i = 0; i < m; ++i){
int u = X[id[i]], v = Y[id[i]];
u = fp(x, u);
v = fp(x, v);
if(u != v){
g[x][nn[x]].push_back(u);
g[x][nn[x]].push_back(v);
p[x][u] = p[x][v] = nn[x];
W[x][nn[x]] = (x == 0 ? min(X[id[i]], Y[id[i]])
: max(X[id[i]], Y[id[i]]));
nn[x]++;
}
}
// FIX: initialize root weight
W[x][nn[x]-1] = (x == 0 ? -1e9 : 1e9);
ti[x] = 0;
fill(arr[x], arr[x] + nn[x], -1);
// FIX: handle disconnected components
for(int i = 0; i < nn[x]; ++i)
if(fp(x, i) == i)
dfs(x, i, i);
for(int i = 0; i < n; ++i)
arr[x][ tin[x][i] ] = i;
}
// FIX: vector instead of map
vector<int> mp(n, -1);
for(int i = 0; i < nn[1]; ++i)
if(arr[1][i] != -1)
mp[arr[1][i]] = i;
for(int i = 0; i < nn[0]; ++i)
if(arr[0][i] != -1)
arr[0][i] = mp[arr[0][i]];
bld(1, 0, nn[0]-1);
int q = S.size();
vector<int> Ans(q);
for(int i = 0; i < q; ++i){
int u = S[i], v = E[i];
int anc_u = -1, anc_v = -1;
// FIX: correct binary search direction
int lo = 0, hi = d[0][u];
while(lo <= hi){
int mid = (lo + hi) >> 1;
int anc = kth(0, u, mid);
if(W[0][anc] >= L[i])
anc_u = anc, hi = mid - 1;
else
lo = mid + 1;
}
lo = 0, hi = d[1][v];
while(lo <= hi){
int mid = (lo + hi) >> 1;
int anc = kth(1, v, mid);
if(W[1][anc] <= R[i])
anc_v = anc, hi = mid - 1;
else
lo = mid + 1;
}
if(anc_u == -1 || anc_v == -1){
Ans[i] = 0;
continue;
}
L1 = tin[0][anc_u];
R1 = tout[0][anc_u];
L2 = tin[1][anc_v];
R2 = tout[1][anc_v];
Ans[i] = qry(1, 0, nn[0]-1) > 0;
}
return Ans;
}
