#include "werewolf.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
typedef std::unordered_map<lld,int>::const_iterator mit;
/*class DFT{
std::unordered_map<lld,int> m;
int N;
public:
void init(int n){
N=n;
//m.rehash(10000);
}
void sum(int a, int b, int x){
lld pos=a*(N+1)+b;
mit it =m.find(pos);
if(it==m.end()){
m[pos]=x;
return;
}
m[pos]=it->second+x;
}
int get(int a, int b){lld pos=a*(N+1)+b;
mit it =m.find(pos);
if(it==m.end()){
return 0;
}
return it->second;
}
void at(int x, int y, int up){
for(int i=x;i<=N;i+=(i&(-i))){
for(int j=y;j<=N;j+=(j&(-j))){
sum(i,j,up);
}
}
}
int query(int x, int y){
int ans=0;
for(int i=x;i>0;i-=(i&(-i))){
for(int j=y;j>0;j-=(j&(-j))){
ans+=get(i,j);
}
}return ans;
}
};*/
class FT{
int arr[1000000];
int N;
public:
void init(int n){
N=n;
//m.rehash(10000);
for(int i=0;i<=n;i++)arr[i]=0;
}
void at(int x, int up){
for(int i=x;i<=N;i+=(i&(-i))){
arr[i]+=up;
}
}
int query(int x){
int ans=0;
for(int i=x;i>0;i-=(i&(-i))){
ans+=arr[i];
}return ans;
}
};
class DSU{
int parent[1000000];
int root[1000000];
int ST[1000000][32];
vector<int> child[1000000];
int TOP;
int MOD;
int N;
public:
vector<int> Tour;
int first[1000000];
int last[1000000];
void init(int n, int mod){
N=n;
for(int i=0;i<n;i++){
parent[i]=i;
root[i]=i;
first[i]=-1;
last[i]=-1;
}
MOD=mod;
}
int Root(int x){
if(x==root[x])return x;
root[x]=Root(root[x]);
return root[x];
}
void merge(int a, int b){
a=Root(a);
b=Root(b);
if(a==b)return;
if(MOD){
if(a<b){
parent[a]=b;
root[a]=b;
}else{
parent[b]=a;
root[b]=a;
}
return;
}
if(a<b){
parent[b]=a;
root[b]=a;
}else{
parent[a]=b;
root[a]=b;
}
return;
}
void arrange(){
for(int i=0;i<N;i++){
if(parent[i]!=i){
child[parent[i]].push_back(i);
}else TOP=i;
}
for(int i=0;i<N;i++){
ST[i][0]=parent[i];
}
for(int j=1;j<32;j++){
for(int i=0;i<N;i++){
ST[i][j]=ST[ST[i][j-1]][j-1];
}
}
}
void DFS(int node){
first[node]=Tour.size();
Tour.push_back(node);
for(int i=0;i<child[node].size();i++){
DFS(child[node][i]);
//Tour.push_back(node);
}
last[node]=Tour.size();
}
void START(){
DFS(TOP);
}
int Query(int Start,int Top){
if(MOD==0){
int ans=Start;
for(int i=31;i>-1;i--){
if(ST[ans][i]>=Top)ans=ST[ans][i];
}
return ans;
}
int ans=Start;
for(int i=31;i>-1;i--){
if(ST[ans][i]<=Top)ans=ST[ans][i];
}
return ans;
}
void CMP(){
for(int i=0;i<Tour.size();i++){
if(first[Tour[i]]==-1)first[Tour[i]]=i;
last[Tour[i]]=i;
}
}
void print(){
/*for(int i=0;i<N;i++){
cout<<parent[i]<<" ";
}cout<<endl;*/
for(int i=0;i<Tour.size();i++){
cout<<Tour[i]<<" ";
}cout<<endl;
}
};
DSU *D1;
DSU *D2;
FT *F;
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 Q = S.size();
std::vector<int> A(Q);
D1=new DSU();D2=new DSU();
D1->init(N,0);
D2->init(N,1);
vector<pair<int,int> > order1;
vector<pair<int,int> > order2;
for(int i=0;i<X.size();i++){
if(X[i]<Y[i]){
order1.push_back(pii(X[i],Y[i]));
order2.push_back(pii(Y[i],X[i]));
}
else{
order1.push_back(pii(Y[i],X[i]));
order2.push_back(pii(X[i],Y[i]));
}
}
sort(order1.begin(),order1.end());
sort(order2.begin(),order2.end());
for(int i=order1.size()-1;i>-1;i--){
//cout<<order1[i].first<<" "<<order1[i].second<<endl;
D1->merge(order1[i].first,order1[i].second);
}D1->arrange();
D1->START();
//D1->CMP();
//D1->print();
for(int i=0;i<order2.size();i++){
D2->merge(order2[i].first,order2[i].second);
}
D2->arrange();
D2->START();
//D2->CMP();
//D2->print();
int Query[Q][4];
F=new FT();
F->init(N);
int per[N];
for(int i=0;i<N;i++){
per[D1->first[i]]=D2->first[i]+1;
}
/*for(int i=0;i<N;i++){
cout<<per[i]<<endl;
}*/
vector<pair<pii,int> >V;
for(int i=0;i<Q;i++){A[i]=0;
Query[i][0]=D1->first[D1->Query(S[i],L[i])];
Query[i][1]=D1->last[D1->Query(S[i],L[i])];
Query[i][2]=D2->first[D2->Query(E[i],R[i])];
Query[i][3]=D2->last[D2->Query(E[i],R[i])];
V.push_back(pair<pii,int>(pii(Query[i][0],Query[i][2]),4*i));
V.push_back(pair<pii,int>(pii(Query[i][1],Query[i][3]),4*i+1));
V.push_back(pair<pii,int>(pii(Query[i][0],Query[i][3]),4*i+2));
V.push_back(pair<pii,int>(pii(Query[i][1],Query[i][2]),4*i+3));
}
sort(V.begin(),V.end());
int pnt=0;
for(int i=0;i<V.size();i++){
//cout<<V[i].first.first<<" "<<V[i].first.second<<" "<<V[i].second<<endl;
while(pnt<V[i].first.first){
pnt++;
F->at(per[pnt-1],1);
}
if((V[i].second%4)<2){
A[V[i].second/4]+=F->query(V[i].first.second);
}else{
A[V[i].second/4]-=F->query(V[i].first.second);
}
}
for (int i = 0; i < Q; ++i) {//cout<<i<<endl;
if(A[i]>0)A[i]=1;
}
return A;
}
