#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=4e5+5;
int dsu[nx], id[nx][2], idx, cnt, l[nx][2], r[nx][2], p[nx][2], res[nx];
vector<int> d[nx], a[nx], ans;
vector<pair<int, int>> c[nx];
vector<tuple<int, int, int>> eds, edt;
struct fenwick
{
int d[nx];
void add(int i)
{
while (i<nx) d[i]++, i+=(i&-i);
}
int find(int i)
{
int res=0;
while (i>0) res+=d[i], i-=(i&-i);
return res;
}
} f;
int find(int x)
{
if (dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
void dfs(int u, int m)
{
//cout<<"dfs "<<u<<'\n';
l[u][m]=INT_MAX;
if (d[u].empty()) return id[u][m]=l[u][m]=r[u][m]=++cnt, void();
for (auto v:d[u]) dfs(v, m), l[u][m]=min(l[u][m], l[v][m]), r[u][m]=max(r[u][m], r[v][m]);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
for (int i=0; i<X.size(); i++) if (X[i]<Y[i]) swap(X[i], Y[i]);
for (int i=0; i<X.size(); i++) eds.push_back({Y[i], 0, X[i]}), edt.push_back({X[i], 0, Y[i]});
for (int i=0; i<S.size(); i++) eds.push_back({L[i], -1, i}), edt.push_back({R[i], 1, i});
sort(eds.begin(), eds.end());
reverse(eds.begin(), eds.end());
sort(edt.begin(), edt.end());
for (int i=0; i<2*N-1; i++) dsu[i]=i;
idx=N;
for (auto [u, t, v]:eds)
{
//cout<<"update "<<u<<' '<<t<<' '<<v<<'\n';
if (t==-1) p[v][0]=find(S[v]); //cout<<"find "<<v<<' '<<S[v]<<' '<<find(S[v])<<'\n';
else if (find(u)!=find(v)) d[idx].push_back(find(u)), d[idx].push_back(find(v)), dsu[find(u)]=dsu[find(v)]=idx++; //cout<<"add edge "<<u<<' '<<v<<' '<<idx<<'\n';
}
dfs(idx-1, 0);
idx=N;
cnt=0;
for (int i=0; i<2*N-1; i++) dsu[i]=i, d[i].clear();
for (auto [u, t, v]:edt)
{
//cout<<"update "<<u<<' '<<t<<' '<<v<<'\n';
if (t==1) p[v][1]=find(E[v]); //cout<<"find "<<v<<' '<<S[v]<<' '<<find(S[v])<<'\n';
else if (find(u)!=find(v)) d[idx].push_back(find(u)), d[idx].push_back(find(v)), dsu[find(u)]=dsu[find(v)]=idx++; //cout<<"add edge "<<u<<' '<<v<<' '<<idx<<'\n';
}
dfs(idx-1, 1);
/*
cout<<"id ";
for (int i=0; i<N; i++) cout<<id[i][1]<<' ';
cout<<'\n';
for (int i=0; i<S.size(); i++) cout<<i<<' '<<p[i]<<' '<<l[p[i]][1]<<' '<<r[p[i]][1]<<'\n';*/
//for (int i=0; i<S.size(); i++) cout<<"range "<<i<<' '<<l[p[i]][0]<<' '<<l[p[i]][1]<<' '<<r[p[]i][0]<<' '<<r[i][1]<<'\n';
for (int i=0; i<S.size(); i++) c[l[p[i][0]][0]-1].push_back({-1, i}), c[r[p[i][0]][0]].push_back({1, i});
for (int i=0; i<N; i++) a[id[i][0]].push_back(id[i][1]);
for (int i=0; i<=N; i++)
{
for (auto y:a[i]) f.add(y);
for (auto [mul, j]:c[i]) res[j]+=(f.find(r[p[j][1]][1])-f.find(l[p[j][1]][1]-1))*mul;
}
for (int i=0; i<S.size(); i++) ans.push_back(res[i]>0);
return ans;
}
