#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
struct event{
int l,r,id;
};
int n,m,q,tt,num[MAXN],to[MAXN],res[MAXN];
vector<int> v[MAXN],mint[MAXN],maxt[MAXN],ans,bro;
int dsu[MAXN],euler[MAXN],from[MAXN],len[MAXN];
int up[MAXN],up2[MAXN];
vector<event> qr[MAXN];
int root(int x){
if(dsu[x]==x)return x;
dsu[x]=root(dsu[x]);
return dsu[x];
}
void setdsu(){
for(int i=1;i<=n;i++){
dsu[i]=i;
}
}
void dfs(int x,int p){
tt++; num[x]=to[x]=tt; up[x]=p;
for(int i=0;i<maxt[x].size();i++){
dfs(maxt[x][i],x);
}
to[x]=tt;
}
void dfs2(int x,int p){
tt++; euler[tt]=num[x];
from[x]=tt; up2[x]=p;
for(int i=0;i<mint[x].size();i++){
dfs2(mint[x][i],x);
}
len[x]=tt;
}
int dp[MAXN][25],dp2[MAXN][25];
bool li[MAXN][25],li2[MAXN][25];
int ff(int x,int p){
if(up[x]==0)return 0;
if(p==0)return up[x];
if(li[x][p])return dp[x][p];
li[x][p]=true;
dp[x][p]=ff(ff(x,p-1),p-1);
return dp[x][p];
}
int ff2(int x,int p){
if(up2[x]==0)return 0;
if(p==0)return up2[x];
if(li2[x][p])return dp2[x][p];
li2[x][p]=true;
dp2[x][p]=ff2(ff2(x,p-1),p-1);
return dp2[x][p];
}
int fenwick[MAXN];
void update(int x){
while(x<=n){
fenwick[x]++;
x+=(x & (-x));
}
}
int sum(int x){
int res=0;
while(x>=1){
res+=fenwick[x];
x-=(x & (-x));
}
return res;
}
void check(int x,int y,int id){
qr[from[y]-1].push_back({num[x],to[x],id});
qr[len[y]].push_back({num[x],to[x],id});
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> T,vector<int> L,vector<int> R){
n=N; m=int(X.size()); q=int(S.size());
for(int i=0;i<m;i++){
X[i]++; Y[i]++;
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
setdsu();
for(int i=n;i>=1;i--){
for(int f=0;f<v[i].size();f++){
if(root(v[i][f])>i){
maxt[i].push_back(root(v[i][f]));
dsu[root(v[i][f])]=i;
}
}
}
dfs(1,0);
setdsu();
for(int i=1;i<=n;i++){
for(int f=0;f<v[i].size();f++){
if(root(v[i][f])<i){
mint[i].push_back(root(v[i][f]));
dsu[root(v[i][f])]=i;
}
}
}
tt=0;
dfs2(n,0);
for(int i=0;i<q;i++){
S[i]++; T[i]++; L[i]++; R[i]++;
for(int f=24;f>=0;f--){
if(ff(S[i],f)!=0 and ff(S[i],f)>=L[i]){
S[i]=ff(S[i],f);
}
}
for(int f=24;f>=0;f--){
if(ff2(T[i],f)!=0 and ff2(T[i],f)<=R[i]){
T[i]=ff2(T[i],f);
}
}
check(S[i],T[i],i);
res[i]=-1;
}
for(int i=0;i<=n;i++){
if(i!=0)update(euler[i]);
for(int f=0;f<qr[i].size();f++){
if(res[qr[i][f].id]==-1){
res[qr[i][f].id]=sum(qr[i][f].r)-sum(qr[i][f].l-1);
}else{
res[qr[i][f].id]=sum(qr[i][f].r)-sum(qr[i][f].l-1)-res[qr[i][f].id];
}
}
}
for(int i=0;i<q;i++){
if(res[i]>0)ans.push_back(1);
else ans.push_back(0);
}
return ans;
}
/*
int main(){
bro=check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
{4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
cout<<bro[0]<<" "<<bro[1]<<" "<<bro[2]<<"\n";
}
*/
