#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<int,int>
const int M=2e5+7;
const int N=4e5+7;
const int LOG=20;
int n;
int trace[M][LOG+10][2],beg[M][2],fin[M][2],id[M][2],pre[2];
vector<int>a[M],minv[M],maxv[M];
struct node
{
int x,y,value,id;
node(int _x=0,int _y=0,int _value=0,int _id=0)
{
x=_x,y=_y,value=_value,id=_id;
}
};
vector<node>query[N];
struct DSU
{
int n;
vector<vector<int> >trace;
DSU(int _n=0)
{
n=_n;
trace.resize(2,vector<int>(n+7));
for(int need=0;need<=1;need++)
{
iota(trace[need].begin(),trace[need].end(),0);
}
}
int get(int x,int index)
{
return trace[index][x]==x?trace[index][x]:trace[index][x]=get(trace[index][x],index);
}
void conncet(int x,int y,int index,vector<int>adj[])
{
int u=get(x,index);
int v=get(y,index);
if(u==v)return ;
trace[index][v]=u;
adj[u].push_back(v);
}
};
void dfs(int x,int cha,int index,vector<int>adj[])
{
pre[index]++;
beg[x][index]=pre[index];
id[pre[index]][index]=x;
for(int node:adj[x])
{
if(node==cha)continue;
trace[node][0][index]=x;
dfs(node,x,index,adj);
}
fin[x][index]=pre[index];
}
void sprase()
{
for(int index=0;index<=1;index++)
{
for(int i=1;i<=LOG;i++)
{
for(int node=1;node<=n;node++)
{
if(trace[node][i-1][index]!=-1)
{
trace[node][i][index]=trace[trace[node][i-1][index]][i-1][index];
}
}
}
}
}
struct IT
{
int n;
vector<int>bit;
IT(int _n=0)
{
n=_n;
bit.assign(n+7,0);
}
void update(int x,int value)
{
for(;x<=n;x+=x&(-x))
{
bit[x]+=value;
}
}
int get(int x)
{
int ans=0;
for(;x;x-=x&(-x))
{
ans+=bit[x];
}
return ans;
}
int get_sum(int x,int y)
{
return get(y)-get(x-1);
}
};
vector<int> check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R)
{
n=N;
for(int i=1;i<=n;i++)
{
for(int node=0;node<=LOG;node++)
{
for(int index=0;index<=1;index++)trace[i][node][index]=-1;
}
}
for(int i=1;i<=(int)X.size();i++)
{
int x=X[i-1]+1;
int y=Y[i-1]+1;
a[x].push_back(y);
a[y].push_back(x);
}
DSU s(n);
for(int i=1;i<=n;i++)
{
for(int node:a[i])if(node<i)
{
s.conncet(i,node,1,maxv);
}
}
for(int i=n;i>=1;i--)
{
for(int node:a[i])if(node>i)
{
s.conncet(i,node,0,minv);
}
}
dfs(1,0,0,minv);
dfs(n,0,1,maxv);
sprase();
int q=(int)L.size();
for(int i=1;i<=q;i++)
{
int x=S[i-1]+1;
int y=E[i-1]+1;
int u=L[i-1]+1;
int v=R[i-1]+1;
for(int node=LOG;node>=0;node--)
{
if(trace[x][node][0]==-1)continue;
if(trace[x][node][0]>=u)x=trace[x][node][0];
}
for(int node=LOG;node>=0;node--)
{
if(trace[y][node][1]==-1)continue;
if(trace[y][node][1]<=v)y=trace[y][node][1];
}
int node_x=beg[x][0]-1;
int node_y=fin[x][0];
query[node_x].push_back({beg[y][1],fin[y][1],-1,i});
query[node_y].push_back({beg[y][1],fin[y][1],1,i});
}
IT bit(n);
vector<int>ans(q);
for(int i=0;i<=n;i++)
{
if(i>0)
{
int new_node=beg[id[i][0]][1];
bit.update(new_node,1);
}
for(node need:query[i])
{
ans[need.id-1]+=need.value*bit.get_sum(need.x,need.y);
//cout<<need.x<<" "<<need.y<<endl;
}
}
for(int i=0;i<=q-1;i++)
{
ans[i]=(ans[i]>0)?1:0;
}
return ans;
}
/*int main()
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
vector<int>x,y,s,e,l,r;
for(int i=1; i<=m; i++)
{
int value_x,value_y;
cin>>value_x>>value_y;
x.push_back(value_x);
y.push_back(value_y);
}
for(int i=1;i<=q;i++)
{
int value_s,value_e,value_l,value_r;
cin>>value_s>>value_e>>value_l>>value_r;
s.push_back(value_s);
e.push_back(value_e);
l.push_back(value_l);
r.push_back(value_r);
}
vector<int> ans=check_validity(n,x,y,s,r,l,r);
for(int node:ans)cout<<node<<endl;
}*/
