#include "werewolf.h"
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=5e5+500;
const ll inf=1e9+900;
ll seg[maxn*4];
void bild(ll l,ll r,ll node){
fill(seg,seg+maxn,inf);
}
ll findMin(ll L,ll R,ll node,ll l,ll r){
ll ans=inf;
for(ll i=l;i<r;i++)ans=min(ans,seg[i]);
return ans;
}
ll update(ll L,ll R,ll node,ll x,ll v){
seg[x]=v;
}
vector<ll> c[2];
ll n,q;
ll kojc1[maxn];
vector<ll> ves[maxn];
vector<ll> findAns(vector<ll> l,vector<ll> r,vector<ll> L,vector<ll> R){
for(ll i=0;i<n;i++){
kojc1[c[1][i]]=i;
}
vector<ll> ans;
ans.resize(q);
for(ll i=0;i<q;i++){
l[i]=max(l[i],0);
r[i]=min(r[i],n);
L[i]=max(L[i],0);
R[i]=min(R[i],n);
if(!(l[i]>=r[i] || L[i]>=R[i])){
ves[l[i]].pb(i);
}
}
bild(0,n,1);
for(ll i=n-1;i>=0;i--){
update(0,n,1,kojc1[c[0][i]],i);
for(auto y:ves[i]){
ll u=findMin(0,n,1,L[y],R[y]);
if(u<r[y]){
ans[y]=1;
}
}
}
return ans;
}
ll m;
vector<ll> ger[maxn];
ll par[maxn];
bool hast[maxn];
vector<ll> tree[2][maxn];
ll st[2][maxn];
ll et[2][maxn];
ll tt=0;
ll cnt=-1;
ll findPar(ll x){
if(par[x]==x)return x;
par[x]=findPar(par[x]);
return par[x];
}
void clearr(){
cnt++;
for(ll i=0;i<maxn;i++){
par[i]=i;
hast[i]=0;
}
}
void add(ll x){
hast[x]=1;
for(auto v:ger[x]){
if(hast[v]){
ll r=findPar(v);
if(r!=x){
par[r]=x;
tree[cnt][x].pb(r);
}
}
}
}
void dfs(ll a,ll b){
c[b].pb(a);
st[b][a]=tt++;
for(auto v:tree[b][a]){
dfs(v,b);
}
et[b][a]=tt;
}
vector<ll> li[maxn];
vector<ll> ri[maxn];
ll lp[maxn];
ll rp[maxn];
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R) {
q = S.size();
m=X.size();
n=N;
for(ll i=0;i<m;i++){
ger[X[i]].pb(Y[i]);
ger[Y[i]].pb(X[i]);
}
for(ll i=0;i<q;i++){
li[L[i]].pb(i);
ri[R[i]].pb(i);
}
clearr();
for(ll i=0;i<n;i++){
add(i);
for(auto x:ri[i]){
rp[x]=findPar(E[x]);
}
}
ll rotr=findPar(0);
clearr();
for(ll i=n-1;i>=0;i--){
add(i);
for(auto x:li[i]){
lp[x]=findPar(S[x]);
}
}
ll rotl=findPar(0);
tt=0;
dfs(rotr,0);
tt=0;
dfs(rotl,1);
vector<ll> A,B,a,b;
A.resize(q);B.resize(q);a.resize(q);b.resize(q);
for(ll i=0;i<q;i++){
ll X=rp[i];
ll Y=lp[i];
a[i]=st[0][X];
b[i]=et[0][X];
A[i]=st[1][Y];
B[i]=et[1][Y];
}
vector<int> ans=findAns(a,b,A,B);
for(ll i=0;i<q;i++){
if(S[i]<L[i] || E[i]>R[i])ans[i]=0;
}
return ans;
}
