#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
#define maxn 400005
int cnt,par[maxn];
void init(int N){
for(int i=0;i<N;++i){
par[i]=i;
}
}
int fp(int i){
return (par[i]==i)?i:par[i]=fp(par[i]);
}
int join(int x,int y){
x=fp(x),y=fp(y);
par[x]=par[y]=cnt;
return cnt++;
}
vi AL1[maxn],AL2[maxn],ord1;
int dfscnt;
int p1[maxn][20],w1[maxn],r1[maxn],pre1[maxn],pst1[maxn];
int p2[maxn][20],w2[maxn],r2[maxn],pre2[maxn],pst2[maxn],pos[maxn];
void dfs1(int u){
pre1[u]=dfscnt;
if(AL1[u].size()==0){
++dfscnt;
ord1.pb(u);
}
for(int v:AL1[u]){
p1[v][0]=u;
dfs1(v);
}
pst1[u]=dfscnt-1;
}
void dfs2(int u){
pre2[u]=dfscnt;
if(AL2[u].size()==0){
++dfscnt;
}
for(int v:AL2[u]){
p2[v][0]=u;
dfs2(v);
}
pst2[u]=dfscnt-1;
}
int n,v[2*maxn];
void up(int i,int s,int e,int x,int nv){
if(s==x&&e==x){v[i]=nv;return;}
int m=(s+e)>>1;
if(x<=m)up(2*i+1,s,m,x,nv);
else up(2*i+2,m+1,e,x,nv);
v[i]=max(v[2*i+1],v[2*i+2]);
}
void up(int x,int nv){
up(0,0,n-1,x,nv);
}
int qry(int i,int s,int e,int x,int y){
if(s==x&&e==y)return v[i];
int m=(s+e)>>1;
if(y<=m)return qry(2*i+1,s,m,x,y);
if(x>m)return qry(2*i+2,m+1,e,x,y);
return max(qry(2*i+1,s,m,x,m),qry(2*i+2,m+1,e,m+1,y));
}
int qry(int x,int y){
return qry(0,0,n-1,x,y);
}
struct query{
int l1,r1,l2,r2,i;
};
vector<query> qrys;
vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R){
int Q=S.size(),M=X.size();
vector<ii> edges;
for(int i=0;i<M;++i){
edges.pb({X[i],Y[i]});
}
sort(all(edges),[](ii &a,ii &b){return min(a.fi,a.se)>min(b.fi,b.se);});
init(2*N);cnt=N;
for(ii pr:edges){
int a=fp(pr.fi),b=fp(pr.se);
if(a!=b){
int p=join(a,b);
w1[p]=min(pr.fi,pr.se);
AL1[p].pb(a);
AL1[p].pb(b);
}
}
sort(all(edges),[](ii &a,ii &b){return max(a.fi,a.se)<max(b.fi,b.se);});
init(2*N);cnt=N;
for(ii pr:edges){
int a=fp(pr.fi),b=fp(pr.se);
if(a!=b){
int p=join(a,b);
w2[p]=max(pr.fi,pr.se);
AL2[p].pb(a);
AL2[p].pb(b);
}
}
memset(p1,-1,sizeof p1);
dfscnt=0;
dfs1(cnt-1);
memset(p2,-1,sizeof p2);
dfscnt=0;
dfs2(cnt-1);
for(int k=1;k<20;++k){
for(int i=0;i<cnt;++i){
if(p1[i][k-1]!=-1)p1[i][k]=p1[p1[i][k-1]][k-1];
if(p2[i][k-1]!=-1)p2[i][k]=p2[p2[i][k-1]][k-1];
}
}
//pf("pre1: ");for(int i=0;i<N;++i)pf("%d ",pre1[i]);pf("\n");
//pf("pre2: ");for(int i=0;i<N;++i)pf("%d ",pre2[i]);pf("\n");
//pf("w1: ");for(int i=0;i<cnt;++i)pf("%d ",w1[i]);pf("\n");
//pf("w2: ");for(int i=0;i<cnt;++i)pf("%d ",w2[i]);pf("\n");
for(int i=0;i<Q;++i){
query q={0,0,0,0,i};
//pf("qry: %d %d %d %d\n",S[i],E[i],L[i],R[i]);
int cur=S[i];
for(int k=19;k>=0;--k){
if(p1[cur][k]!=-1&&w1[p1[cur][k]]>=L[i])cur=p1[cur][k];
}
q.l1=pre1[cur];
q.r1=pst1[cur];
cur=E[i];
for(int k=19;k>=0;--k){
if(p2[cur][k]!=-1&&w2[p2[cur][k]]<=R[i])cur=p2[cur][k];
}
q.l2=pre2[cur];
q.r2=pst2[cur];
//pf("%d %d %d %d\n",q.l1,q.r1,q.l2,q.r2);
qrys.pb(q);
}
vi A(Q,0);
sort(all(qrys),[](query &a,query &b){return a.r1<b.r1;});
n=N;memset(v,-1,sizeof v);
int pv=-1;
for(int i=0;i<Q;++i){
query &q=qrys[i];
while(pv<q.r1){
++pv;
int x=ord1[pv];//node index
int pos=pre2[x];//preorder
up(pos,pv);
}
int val=qry(q.l2,q.r2);
if(val>=q.l1)A[q.i]=1;
}
return A;
}
