#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define task "werewolf"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
int pos[100010],lz[100010];
int mn[100010][20],mx[100010][20];
vector<int> ad[100010];
int gmin(int i,int j){
int t=lz[j-i+1];
return min(mn[i][t],mn[j-(1<<t)+1][t]);
}
int gmax(int i,int j){
int t=lz[j-i+1];
return max(mx[i][t],mx[j-(1<<t)+1][t]);
}
vector<int> check_validity(int n, vector<int>x, vector<int>y, vector<int>s, vector<int>t, vector<int>l, vector<int>r){
forinc(i,1,n) lz[i]=log2(i);
forinc(i,0,x.size()-1){
ad[x[i]].pb(y[i]);
ad[y[i]].pb(x[i]);
}
int st=0,pr=0; while(ad[st].size()>1) st++;
vector<int> a;
for(;;){
int ok=0;
a.pb(st); pos[st]=a.size();
forv(v,ad[st]) if(v!=pr){
ok=1;
pr=st;
st=v;
}
if(!ok) break;
}
forinc(i,1,n) mn[i][0]=mx[i][0]=a[i-1];
forinc(j,1,18) forinc(i,1,n){
if(i+(1<<j)>n+1) break;
mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
}
vector<int> ret;
forinc(i,0,l.size()-1){
if(s[i]<l[i] || t[i]>r[i]){
ret.pb(0);
continue;
}
int st=s[i],ed=t[i];
int le,ri,X,Y;
if(pos[st]<=pos[ed]){
le=st,ri=ed;
while(le<=ri){
int mi=(le+ri)/2;
if(gmin(le,mi)>=l[i]) X=mi,le=mi+1;
else ri=mi-1;
}
le=st,ri=ed;
while(le<=ri){
int mi=(le+ri)/2;
if(gmax(mi,ri)<=r[i]) Y=mi,ri=mi-1;
else le=mi+1;
}
} else{
le=ed,ri=st;
while(le<=ri){
int mi=(le+ri)/2;
if(gmax(le,mi)<=r[i]) X=mi,le=mi+1;
else ri=mi-1;
}
le=ed,ri=st;
while(le<=ri){
int mi=(le+ri)/2;
if(gmin(mi,ri)>=l[i]) Y=mi,ri=mi-1;
else le=mi+1;
}
}
ret.pb(X>=Y);
}
return ret;
}
