#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn=200000+5;
vector<int>adj[maxn];
struct dsu{
int par[maxn],sz[maxn],lca[maxn][20],fpar[maxn];
vector<int>child[maxn];
pair<int,int>stf[maxn];
int timea;
dsu(){
for(int i=0;i<maxn;i++){
for(int j=0;j<20;j++){
lca[i][j]=-1;
}
}
timea=0;
for(int i=0;i<maxn;i++){
par[i]=i;
fpar[i]=i;
}
}
int root(int c){
if(fpar[c]==c){
return c;
}
return fpar[c]=root(fpar[c]);
}
void con(int u,int v,int vv){
int rootu=root(u),rootv=root(v);
if(rootu!=rootv){
if(vv==0){
if(rootu<rootv){
swap(rootu,rootv);
}
}
else{
if(rootu>rootv){
swap(rootu,rootv);
}
}
par[rootv]=rootu;
child[rootu].push_back(rootv);
fpar[rootv]=rootu;
}
}
void dfs(int u){
timea++;
stf[u].first=timea;
for(auto x:child[u]){
lca[x][0]=u;
// cout<<u<<" "<<x<<" "<<timea<<endl;
dfs(x);
}
stf[u].second=timea;
}
void build(){
int rishe=root(1);
dfs(rishe);
for(int i=1;i<20;i++){
for(int j=0;j<maxn;j++){
if(lca[j][i-1]==-1){
continue;
}
lca[j][i]=lca[lca[j][i-1]][i-1];
}
}
}
int ww(int u,int had,int vv){
for(int i=19;i>=0;i--){
if(lca[u][i]!=-1){
// cout<<u<<" "<<vv<<" "<<lca[u][i]<<endl;
if(vv==0){
if(lca[u][i]<=had){
u=lca[u][i];
}
}
else{
if(lca[u][i]>=had){
u=lca[u][i];
}
}
}
}
return u;
}
};
int kaf=(1<<18);
struct segment{
struct node{
vector<int>all;
};
node seg[(1<<19)];
vector<int>merge(vector<int>a,vector<int>b){
vector<int>ret;
int i=0,j=0;
while(i<(int)a.size()&&j<(int)b.size()){
if(a[i]<b[j]){
ret.push_back(a[i]);
i++;
}
else{
ret.push_back(b[j]);
j++;
}
}
while(i<(int)a.size()){
ret.push_back(a[i]);
i++;
}
while(j<(int)b.size()){
ret.push_back(b[j]);
j++;
}
return ret;
}
void build(int i){
if((i<<1)>=(1<<19)){
return ;
}
build((i<<1));
build((i<<1)^1);
seg[i].all=merge(seg[(i<<1)].all,seg[(i<<1)^1].all);
}
int pors(int i,int l,int r,int tl,int tr,int hl,int hr){
if(l>tr||r<tl){
return 0;
}
if(l>=tl&&r<=tr){
int p=lower_bound(seg[i].all.begin(),seg[i].all.end(),hl)-seg[i].all.begin();
// cout<<l<<" dsa "<<r<<" "<<tl<<" "<<tr<<" "<<hl<<" "<<hr<<endl;
// for(auto x:seg[i].all){
// cout<<x<<" ";
// }
// cout<<"by"<<endl;
if(p==(int)seg[i].all.size()){
return 0;
}
if(seg[i].all[p]<=hr){
return 1;
}
return 0;
}
int m=(l+r)>>1;
int d=pors((i<<1),l,m,tl,tr,hl,hr);
d|=pors((i<<1)^1,m+1,r,tl,tr,hl,hr);
return d;
}
};
dsu a,b;
segment seg;
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 m=x.size();
for(int i=0;i<m;i++){
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
for(int i=0;i<=n-1;i++){
for(auto x:adj[i]){
if(x<=i){
a.con(x,i,0);
}
}
}
for(int i=n-1;i>=0;i--){
for(auto x:adj[i]){
if(x>=i){
b.con(x,i,1);
}
}
}
a.build();
b.build();
for(int i=0;i<n;i++){
seg.seg[kaf+a.stf[i].first].all.push_back(b.stf[i].first);
// cout<<i<<" asd "<<a.stf[i].first<<" "<<b.stf[i].first<<endl;
}
seg.build(1);
int q=s.size();
vector<int>res(q);
for(int i=0;i<q;i++){
int u=s[i],v=e[i],tl=l[i],tr=r[i];
if(u<tl||v>tr){
res[i]=0;
continue;
}
int bu=b.ww(u,tl,1),bv=a.ww(v,tr,0);
int d=seg.pors(1,0,kaf-1,a.stf[bv].first,a.stf[bv].second,b.stf[bu].first,b.stf[bu].second);
res[i]=d;
// cout<<bu<<" "<<bv<<" "<<u<<" "<<v<<" "<<tl<<" "<<tr<<endl;
}
return res;
}
