#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50,lg=19;
struct DSU{
int par[N+50],in[N+50],out[N+50],nc,a[N+50],Par[N+50][lg+1],sajz[N+50];
vector<int>E[N+50];
void Init(){for(int i=0;i<=N;i++)par[i]=i,nc=0,sajz[i]=1;}
int FS(int u){if(par[u]==u) return u;return par[u]=FS(par[u]);}
void US(int u,int v){par[FS(u)]=FS(v);}//{if(sajz[u]>sajz[v]) swap(u,v);par[v]=u;sajz[v]+=sajz[u];}
void AddEdge(int u,int v){if(u!=v){E[u].pb(v),E[v].pb(u);}}
void DFS(int u,int parent){
//printf("%i %i\n",u-1,parent-1);
in[u]=++nc;a[nc]=u;Par[u][0]=parent;
for(int i=1;i<=lg;i++) Par[u][i]=Par[Par[u][i-1]][i-1];
for(auto i:E[u]) if(i!=parent) DFS(i,u);
out[u]=nc;
}
int NadjiL(int u,int x){for(int i=lg;i>=0;i--) if(Par[u][i] && Par[u][i]<=x) u=Par[u][i];return u;}
int NadjiR(int u,int x){for(int i=lg;i>=0;i--) if(Par[u][i]>=x) u=Par[u][i];return u;}
}dsu[2];
int ind[N+50];
vector<int>E[N+50];
vector<array<int,5> >Qs;
vector<array<int,5> >ev[N+50];
int T[N+50];
void Update(int i,int qval){for(;i<=N;i+=i&-i)T[i]+=qval;}
int Get(int i){int res=0;for(;i>=1;i-=i&-i)res+=T[i];return res;}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,std::vector<int> U, std::vector<int> V,std::vector<int> L, std::vector<int> R) {
int q=U.size();
for(int i=0;i<q;i++) U[i]++,V[i]++,L[i]++,R[i]++;
for(int i=0;i<X.size();i++){
X[i]++,Y[i]++;
int u=X[i],v=Y[i];
E[u].pb(v);E[v].pb(u);
}
dsu[0].Init(),dsu[1].Init();
for(int i=1;i<=n;i++){
for(auto j:E[i]) if(j<i && dsu[0].FS(j)!=dsu[0].FS(i)) {dsu[0].AddEdge(dsu[0].FS(j),i);dsu[0].US(j,i);}
//for(int j=1;j<=n;j++) printf("%i %i\n",dsu[0].par[j]-1,j-1);printf("\n");
}
dsu[0].DFS(n,0);
//printf("\n");
for(int i=n;i>=1;i--) for(auto j:E[i]) if(j>i && dsu[1].FS(j)!=dsu[1].FS(i)) {dsu[1].AddEdge(dsu[1].FS(j),i);dsu[1].US(j,i);}
dsu[1].DFS(1,0);
//for(int i=1;i<=n;i++) printf("%i ",dsu[0].a[i]-1);printf("\n");
//for(int i=1;i<=n;i++) printf("%i %i\n",dsu[0].in[i],dsu[0].out[i]);printf("\n");
for(int i=1;i<=n;i++) ind[dsu[1].a[i]]=i;
vector<int>res(q,0);
for(int I=0;I<q;I++){
int u=U[I],v=V[I],l=L[I],r=R[I];
int v1=dsu[0].NadjiL(v,r),u1=dsu[1].NadjiR(u,l);
Qs.pb({dsu[0].in[v1],dsu[0].out[v1],dsu[1].in[u1],dsu[1].out[u1],I});
ev[dsu[0].in[v1]-1].pb({dsu[1].in[u1],dsu[1].out[u1],I,-1});
ev[dsu[0].out[v1]].pb({dsu[1].in[u1],dsu[1].out[u1],I,1});
}
for(int i=1;i<=n;i++){
Update(ind[dsu[0].a[i]],1);
for(auto j:ev[i]){
int bul=j[3];
res[j[2]]+=bul*(Get(j[1])-Get(j[0]-1));
}
}
for(int i=0;i<q;i++) if(res[i]) res[i]=1;
return res;
}
