#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
int n,m,q,tt,num[MAXN],to[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];
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 check(int x,int y){
for(int i=from[y];i<=len[y];i++){
if(euler[i]>=num[x] and euler[i]<=to[x])return 1;
}
return 0;
}
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;
}
}
}
dfs2(n,0);
for(int i=0;i<q;i++){
S[i]++; T[i]++; L[i]++; R[i]++;
while(S[i]!=1 and up[S[i]]>=L[i]){
S[i]=up[S[i]];
}
while(T[i]!=n and up2[T[i]]<=R[i]){
T[i]=up2[T[i]];
}
ans.push_back(check(S[i],T[i]));
}
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";
}
*/
