#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=6e5+10;
const int L=20;
const int SS=1<<20;
vector<int>graf[N];
int seg[SS*2+10],jump[N][L+1];
int val[N][L+1];
vector<pair<int,int> >tr[N];
pair<int,int>pp[N];
int fau[N],num[N];
vector<pair<int,int> >tr2[N];
int jump2[N][L+1];
int val2[N][L+1];
int li;
int pre[N];
int m;
int naj[N],naj2[N];
vector<int>zap[N];
void add(int a,int ind){
seg[ind+=SS]=a;
for(ind>>=1;ind>0;ind>>=1) seg[ind]=max(seg[ind*2],seg[ind*2+1]);
}
int Query(int a,int b){
int res=0;
for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
if(!(a&1)) res=max(res,seg[a+1]);
if(b&1) res=max(res,seg[b-1]);
}
return res;
}
void dfs(int v,int o,int x=INT_MAX){
jump[v][0]=o;
val[v][0]=x;
for(int i=1;i<=L;i++) jump[v][i]=jump[jump[v][i-1]][i-1],val[v][i]=min(val[v][i-1],val[jump[v][i-1]][i-1]);
li++;
pp[v].fi=li;
for(auto u:tr[v]){
if(u.fi==o) continue;
dfs(u.fi,v,u.se);
}
pp[v].se=li;
}
int zn(int a,int c){
int res=a;
for(int i=L;i>=0;i--)
if(val[a][i]>=c) res=jump[a][i],a=jump[a][i];
return res;
}
int Find(int a){
if(fau[a]==a) return a;
return fau[a]=Find(fau[a]);
}
void Union(int a,int b,int c,int xd){
a=Find(a),b=Find(b);
if(a==b) return;
tr[xd].push_back({num[b],c}),tr[xd].push_back({num[a],c});
fau[a]=b;
num[b]=xd;
}
void Union2(int a,int b,int c,int xd){
a=Find(a),b=Find(b);
if(a==b) return;
tr2[xd].push_back({num[b],c}),tr2[xd].push_back({num[a],c});
fau[a]=b;
num[b]=xd;
}
void dfs2(int v,int o,int x=0){
jump2[v][0]=o,val2[v][0]=x;
if(v<=m) pre[++li]=v;
else ++li;
for(int i=1;i<=L;i++) jump2[v][i]=jump2[jump2[v][i-1]][i-1],val2[v][i]=max(val2[v][i-1],val2[jump2[v][i-1]][i-1]);
naj2[v]=INT_MAX;
int xd=li;
for(auto u:tr2[v]){
if(u.fi==o) continue;
dfs2(u.fi,v,u.se);
naj2[v]=min(naj2[v],naj2[u.fi]);
naj[v]=max(naj[v],naj[u.fi]);
}
if(naj[v]==0) naj2[v]=xd,naj[v]=xd;
}
int zn2(int a,int c){
int res=a;
for(int i=L;i>=0;i--)
if(val2[a][i]<=c) res=jump2[a][i],a=jump2[a][i];
return res;
}
vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l, vector<int> r){
m=n;
vector<int>res(s.size());
for(int i=0;i<(int)s.size();i++) s[i]++,e[i]++,l[i]++,r[i]++;
for(int i=0;i<(int)x.size();i++) x[i]++,y[i]++,graf[x[i]].push_back(y[i]),graf[y[i]].push_back(x[i]);
int wsk=n;
for(int i=1;i<=n;i++) fau[i]=i,num[i]=i;
for(int i=n;i>=1;i--){
for(auto u:graf[i])
if(u>i&&Find(i)!=Find(u)) Union(i,u,i,++wsk);
}
for(int i=1;i<=n;i++) fau[i]=i,num[i]=i;
dfs(wsk,wsk);
wsk=n,li=0;
for(int i=1;i<=n;i++){
for(auto u:graf[i])
if(u<i&&Find(i)!=Find(u)) Union2(i,u,i,++wsk);
}
dfs2(wsk,wsk);
for(int i=0;i<(int)s.size();i++){
int xd=zn2(e[i],r[i]);
zap[naj[xd]].push_back(i);
}
for(int i=1;i<=wsk;i++){
if(pre[i]==0) continue;
add(i,pp[pre[i]].fi);
for(auto u:zap[i]){
int lew=naj2[zn2(e[u],r[u])];
int w=zn(s[u],l[u]);
int xd=Query(pp[w].fi,pp[w].se);
if(xd>=lew) res[u]=1;
else res[u]=0;
}
}
return res;
}
/*int main(){
//vector<int> v=check_validity(4,{1,2,3,4,3,5},{1,2,3,4,0,2},{4,4,5},{2,2,4},{1,2,3},{2,2,4});
//for(auto u:v) cout<<u<<"\n";
} */
