#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vi;
vi ans;
int N;
vi X, Y, S, E, L, R;
vi V[200010];
int t1[400010], t2[400010];
int top;
int par[200010]; int dep[200010];
int im[200010];
pii ar[200010];
struct Query {
int s, l; //e, r
int n, nd;
};
struct tree {
vi child[400010];
int s[400010], e[400010];
int tp=0;
void dfs(int now) {
s[now]=e[now]=tp; tp++;
for (int i:child[now]) {
dfs(i);
s[now]=min(s[now], s[i]);
e[now]=max(e[now], e[i]);
}
}
}tS, tE;
Query Qs[200010], Qe[200010];
bool cmp1(Query q1, Query q2) {return q1.l>q2.l;}
bool cmp2(Query q1, Query q2) {return q1.l<q2.l;}
bool cmp3(Query q1, Query q2) {return q1.n<q2.n;}
void Union(int a, int b, bool type) {
while (par[a]) a=par[a];
while (par[b]) b=par[b];
if (a==b) return ;
if (dep[a]<dep[b]) swap(a, b);
par[b]=a; dep[a]=max(dep[a], dep[b]+1);
if (!type) t1[im[a]]=top, t1[im[b]]=top, tS.child[top].push_back(im[a]), tS.child[top].push_back(im[b]);
else t2[im[a]]=top, t2[im[b]]=top, tE.child[top].push_back(im[a]), tE.child[top].push_back(im[b]);
im[a]=top++;
}
void f1() {
top=N;
memset(dep, 0, sizeof(dep));
memset(par, 0, sizeof(par));
for (int i=0; i<N; i++) im[i]=i;
for (int i=N-1, k=0; i>=0; i--) {
for (int j:V[i]) {
if (j<i) continue;
Union(i, j, false);
}
for (; k<S.size() && i==Qs[k].l; k++) {
if (Qs[k].s<i) {Qs[k].nd=Qs[k].s; continue;}
int l=Qs[k].s; while(par[l]) l=par[l];
Qs[k].nd=im[l];
}
}
tS.dfs(top-1);
}
void f2() {
top=N;
memset(dep, 0, sizeof(dep));
memset(par, 0, sizeof(par));
for (int i=0; i<N; i++) im[i]=i;
for (int i=0, k=0; i<N; i++) {
for (int j:V[i]) {
if (j>i) continue;
Union(i, j, true);
}
for (; k<S.size() && i==Qe[k].l; k++) {
if (Qe[k].s>i) {Qe[k].nd=Qe[k].s; continue;}
int l=Qe[k].s; while(par[l]) l=par[l];
Qe[k].nd=im[l];
}
}
tE.dfs(top-1);
}
struct fQ_ {
int x1, x2, y1, y2;
int Qn, ans;
}fQ[200010];
int seg[(1<<19)];
bool cmp4(fQ_ q1, fQ_ q2) {return q1.x2<q2.x2;}
bool cmp5(fQ_ q1, fQ_ q2) {return q1.Qn<q2.Qn;}
vi check_validity(int N_, vi X_, vi Y_, vi S_, vi E_, vi L_, vi R_) {
N=N_; X=X_; Y=Y_; S=S_; E=E_; L=L_; R=R_;
for (int i=0; i<X.size(); i++) {
V[X[i]].push_back(Y[i]);
V[Y[i]].push_back(X[i]);
}
for (int i=0; i<S.size(); i++) {
Qs[i]={S[i],L[i],i};
Qe[i]={E[i],R[i],i};
}
sort(Qs, Qs+S.size(), cmp1);
sort(Qe, Qe+S.size(), cmp2);
f1(); f2();
sort(Qs, Qs+S.size(), cmp3);
sort(Qe, Qe+S.size(), cmp3);
int nd1, nd2;
for (int i=0; i<S.size(); i++) {
nd1=Qs[i].nd; nd2=Qe[i].nd;
fQ[i]={tS.s[nd1], tS.e[nd1], tE.s[nd2], tE.e[nd2], i, 0};
}
sort(fQ, fQ+S.size(), cmp4);
for (int i=0; i<N; i++) {
assert(tS.s[i]==tS.e[i]);
assert(tE.s[i]==tE.e[i]);
ar[i]={tS.s[i], tE.s[i]};
}
sort(ar, ar+N);
int t=0;
int fr, re, mx;
for (int i=0; i<S.size(); i++) {
for (; t<N&&ar[t].fi<=fQ[i].x2; t++) {
for (int j=(1<<18)+ar[t].se; j; j/=2) seg[j]=max(seg[j], ar[t].fi);
}
fr=fQ[i].y1+(1<<18), re=fQ[i].y2+(1<<18), mx=0;
while (fr<=re) {
if (fr%2) mx=max(mx, seg[fr++]);
if (re%2==0) mx=max(mx, seg[re--]);
fr/=2; re/=2;
}
if (mx>=fQ[i].x1) fQ[i].ans=1;
else fQ[i].ans=0;
}
sort(fQ, fQ+S.size(), cmp5);
for (int i=0; i<S.size(); i++) ans.push_back(fQ[i].ans);
return ans;
}
