#include<bits/stdc++.h>
using namespace std;
#define N cac
const int N=2e5+2;
vector<int> head[N];
int posL[N],bit[N],posR[N];
pair<int,int> idxL[N],idxR[N];
vector<int> adj[N];
vector<pair<int,int> > queryL[N],queryR[N],edgeL[N],edgeR[N];
vector<pair<pair<int,int>,pair<int,bool> > > lis[N];
void upd(int pos){
while(pos<N){
bit[pos]++;
pos+=(pos&-pos);
}
}
int get(int pos){
int sum=0;
while(pos){
sum+=bit[pos];
pos-=(pos&-pos);
}
return sum;
}
int getsum(int x,int y){
return get(y)-get(x-1);
}
int findd(int x){
if(head[x].size()>1){
return x;
}
if(head[x][0]==x){
return x;
}
int y=findd(head[x][0]);
head[x][0]=y;
return y;
}
void unionn(int x,int y){
x=findd(x),y=findd(y);
if(head[x].size()<head[y].size()){
swap(x,y);
}
for(int i:head[y]){
head[x].push_back(i);
}
head[y].clear();
head[y].push_back(x);
}
bool samee(int x,int y){
return findd(x)==findd(y);
}
#undef N
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
int i,j,k,l,n=N,m=X.size(),q=S.size();
vector<int> ans(q);
for(i=0;i<m;i++){
edgeL[min(X[i],Y[i])].push_back({X[i],Y[i]});
edgeR[max(X[i],Y[i])].push_back({X[i],Y[i]});
}
for(i=0;i<n;i++){
head[i].push_back(i);
}
for(i=0;i<q;i++){
queryL[L[i]].push_back({S[i],i});
queryR[R[i]].push_back({E[i],i});
}
for(i=n-1;i>-1;i--){
for(auto x:edgeL[i]){
if(!samee(x.first,x.second)){
unionn(x.first,x.second);
}
}
for(auto x:queryL[i]){
j=findd(x.first);
// cout<<x.second<<'\n';
// for(int y:head[j]){
// cout<<y<<' ';
// }
// cout<<'\n';
idxL[x.second]={head[j][0],head[j].back()};
}
}
j=findd(1);
assert(head[j].size()==n);
for(i=0;i<n;i++){
posL[head[j][i]]=i;
}
for(i=0;i<n;i++){
head[i].clear();
head[i].push_back(i);
}
for(i=0;i<n;i++){
for(auto x:edgeR[i]){
if(!samee(x.first,x.second)){
unionn(x.first,x.second);
}
}
for(auto x:queryR[i]){
j=findd(x.first);
// cout<<x.second<<'\n';
// for(int y:head[j]){
// cout<<y<<' ';
// }
// cout<<'\n';
idxR[x.second]={head[j][0],head[j].back()};
}
}
j=findd(1);
assert(head[j].size()==n);
for(i=0;i<n;i++){
posR[head[j][i]]=i;
}
for(i=0;i<q;i++){
idxL[i]={posL[idxL[i].first],posL[idxL[i].second]};
idxR[i]={posR[idxR[i].first],posR[idxR[i].second]};
assert(idxL[i].first<=idxL[i].second);
assert(idxR[i].first<=idxR[i].second);
lis[idxR[i].second].push_back({idxL[i],{i,true}});
if(idxR[i].first){
lis[idxR[i].first-1].push_back({idxL[i],{i,false}});
}
}
for(i=0;i<n;i++){
upd(posL[head[j][i]]+1);
for(auto x:lis[i]){
if(!x.second.second){
ans[x.second.first]-=getsum(x.first.first+1,x.first.second+1);
}
else{
ans[x.second.first]+=getsum(x.first.first+1,x.first.second+1);
}
}
}
for(i=0;i<q;i++){
// cout<<ans[i]<<endl;
if(ans[i]>0){
ans[i]=1;
}
}
return ans;
}
//int main(){
// vector<int> oh=check_validity({6},{5,1,1,3,3,5},{1,2,3,4,0,2},{4,4,5,3},{2,2,4,4},{1,2,3,3},{2,2,4,4});
// cout<<oh.size()<<" ANS"<<endl;
// for(int i:oh){
// cout<<i<<'\n';
// }
//}
