#include "werewolf.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
//#include "werewolf.h"
using namespace std;
int sef[300005];
int cnt[300005];
int x[600005];
int y[600005];
vector<int>adj[200005];
vector<int>tree1[200005];
vector<int>tree2[200005];
int find(int a)
{
if(sef[a]==a)
{
return a;
}
return sef[a]=find(sef[a]);
}
void merge(int a,int b)
{
a=find(a);
b=find(b);
sef[b]=a;
}
int in1[200005];
int out1[200005];
int timp1=0;
void dfs1(int curr)
{
timp1++;
in1[curr]=timp1;
for(auto k:tree1[curr])
{
dfs1(k);
}
out1[curr]=timp1;
}
int in2[200005];
int out2[200005];
int timp2=0;
void dfs2(int curr)
{
timp2++;
in2[curr]=timp2;
for(auto k:tree2[curr])
{
dfs2(k);
}
out2[curr]=timp2;
}
int st1[200005];
int st2[200005];
int dr1[200005];
int dr2[200005];
int can1[200005];
int can2[200005];
int aib[200005];
vector<pair<int,int>>qu1[200005];
vector<pair<int,int>>qu2[200005];
int nmax=200000;
void update(int poz,int val)
{
while(poz<=nmax)
{
aib[poz]+=val;
poz=poz+(poz&(-poz));
}
}
int query(int poz)
{
int sum=0;
while(poz)
{
sum+=aib[poz];
poz=poz-(poz&(-poz));
}
return sum;
}
int rasp[200005];
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) {
int n=N,dim;
int m=X.size();
int q=S.size();
for(int i=0;i<m;i++)
{
x[i]=X[i];
y[i]=Y[i];
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i=0;i<q;i++)
{
qu1[R[i]].push_back({E[i],i});
qu2[L[i]].push_back({S[i],i});
}
for(int i=0;i<n;i++)
{
sef[i]=i;
}
for(int i=0;i<n;i++)
{
for(auto j:adj[i])
{
if(j<i)
{
if(find(i)!=find(j))
{
//cout<<"muhc "<<i<<" "<<find(j)<<'\n';
tree1[i].push_back(find(j));
merge(i,j);
}
}
}
for(auto j:qu1[i])
{
can1[j.second]=find(j.first);
//cout<<"query"<<" "<<j.second<<" "<<j.first<<" "<<can1[j.second]<<'\n';
}
}
dfs1(n-1);
for(int i=0;i<n;i++)
{
sef[i]=i;
}
for(int i=n-1;i>=0;i--)
{
for(auto j:adj[i])
{
if(j>i)
{
if(find(i)!=find(j))
{
//cout<<"muhc "<<i<<" "<<find(j)<<'\n';
tree2[i].push_back(find(j));
merge(i,j);
}
}
}
for(auto j:qu2[i])
{
can2[j.second]=find(j.first);
//cout<<"query"<<" "<<j.second<<" "<<j.first<<" "<<can1[j.second]<<'\n';
}
}
dfs2(0);
vector<int>rez;
vector<pair<int,int> >ev;
for(int i=0;i<q;i++)
{
//cout<<in1[can1[i]]<<" "<<out1[can1[i]]<<" "<<in2[can2[i]]<<" "<<out2[can2[i]]<<'\n';
int gas=0;
ev.push_back({in2[can2[i]],-i});
ev.push_back({out2[can2[i]]+1,-i});
}
for(int i=0;i<n;i++)
{
ev.push_back({in2[i],in1[i]});
}
sort(ev.begin(),ev.end());
for(auto j:ev)
{
if(j.second<=0)
{
int id=-j.second;
rasp[id]^=(query(out1[can1[id]])-query(in1[can1[id]]-1));
}
else
{
update(j.second,1);
}
}
for(int i=0;i<q;i++)
{
if(rasp[i]==0)
{
rez.push_back(0);
}
else
{
rez.push_back(1);
}
}
return rez;
}
