#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+10;
vector<int> eL[MAXN];
vector<int> eR[MAXN];
vector<pii> queryL[MAXN];
vector<pii> queryR[MAXN];
vector<int> add[MAXN];
vector<pii> query[MAXN];
vector<int> qid[MAXN];
vector<vector<int> > graphL;
vector<vector<int> > graphR;
int Lv[MAXN];
int Rv[MAXN];
int par[MAXN];
int id[MAXN];
int inL[MAXN];
int outL[MAXN];
int inR[MAXN];
int outR[MAXN];
int cal[MAXN];
int tree[MAXN*4];
int seq;
int root(int x){
if(par[x]==x)return x;
return par[x] = root(par[x]);
}
void dfsL(int here){
inL[here] = seq;
seq++;
for(int i=0;i<(int)graphL[here].size();i++){
dfsL(graphL[here][i]);
}
outL[here] = seq-1;
return;
}
void dfsR(int here){
inR[here] = seq;
seq++;
for(int i=0;i<(int)graphR[here].size();i++){
dfsR(graphR[here][i]);
}
outR[here] = seq-1;
return;
}
inline void update(int tmp){
while(tmp){
tree[tmp]++;
tmp>>=1;
}
}
inline int getans(int L,int R){
int res = 0;
while(L<=R){
if(L&1){
res += tree[L];
L++;
}
if(!(R&1)){
res += tree[R];
R--;
}
L>>=1; R>>=1;
}
return res;
}
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 M = (int)X.size();
int Q = (int)L.size();
int x,y;
for(int i=0;i<M;i++){
x = X[i];
y = Y[i];
if(x>y)swap(x,y);
eR[x].push_back(y);
eL[y].push_back(x);
}
for(int i=0;i<Q;i++){
queryL[R[i]].push_back(pii(E[i],i));
queryR[L[i]].push_back(pii(S[i],i));
}
int NN = (N<<1);
graphL = vector<vector<int> > (NN);
graphR = vector<vector<int> > (NN);
int num = N-1;
for(int i=0;i<N;i++){
par[i] = i;
id[i] = i;
}
int cur,idx;
int curid;
for(int i=0;i<N;i++){
for(int j=0;j<(int)eL[i].size();j++){
curid = root(eL[i][j]);
if(curid^i){
par[curid] = i;
num++;
graphL[num].push_back(id[i]);
graphL[num].push_back(id[curid]);
id[i] = num;
}
}
for(int j=0;j<(int)queryL[i].size();j++){
cur = queryL[i][j].f;
idx = queryL[i][j].s;
cur = root(cur);
Lv[idx] = id[cur];
}
}
num = N-1;
for(int i=0;i<N;i++){
par[i] = i;
id[i] = i;
}
for(int i=N-1;i>=0;i--){
for(int j=0;j<(int)eR[i].size();j++){
curid = root(eR[i][j]);
if(curid^i){
par[curid] = i;
num++;
graphR[num].push_back(id[i]);
graphR[num].push_back(id[curid]);
id[i] = num;
}
}
for(int j=0;j<(int)queryR[i].size();j++){
cur = queryR[i][j].f;
idx = queryR[i][j].s;
cur = root(cur);
Rv[idx] = id[cur];
}
}
/*
for(int i=N;i<=((N-1)<<1);i++){
for(int j=0;j<(int)graphL[i].size();j++){
cout<<graphL[i][j]<<" ";
}
cout<<"\n";
}
cout<<"\n";
for(int i=N;i<=((N-1)<<1);i++){
for(int j=0;j<(int)graphR[i].size();j++){
cout<<graphR[i][j]<<" ";
}
cout<<"\n";
}
cout<<"\n";*/
/*
for(int i=0;i<Q;i++){
cout<<Lv[i]<<" "<<Rv[i]<<"\n";
}*/
seq = 0;
dfsL(((N-1)<<1));
seq = 0;
dfsR(((N-1)<<1));
int la,ra,lb,rb;
for(int i=0;i<Q;i++){
la = inL[Lv[i]];
ra = outL[Lv[i]];
lb = inR[Rv[i]];
rb = outR[Rv[i]];
if(la){
query[la-1].push_back(pii(lb,rb));
qid[la-1].push_back((i<<1));
}
query[ra].push_back(pii(lb,rb));
qid[ra].push_back((i<<1)|1);
}
for(int i=0;i<N;i++){
add[inL[i]].push_back(inR[i]);
}
int base = 1;
for(;base<NN;base<<=1);
int sz = 0;
for(int i=0;i<NN;i++){
sz = (int)add[i].size();
for(int j=0;j<sz;j++){
update(base+add[i][j]);
}
sz = (int)query[i].size();
for(int j=0;j<sz;j++){
idx = qid[i][j];
cur = getans(base+query[i][j].f,base+query[i][j].s);
if(idx&1){
cal[(idx>>1)]+=cur;
}
else {
cal[(idx>>1)]-=cur;
}
}
}
vector<int> ans;
ans = vector<int> (Q);
for(int i=0;i<Q;i++){
if(cal[i])ans[i] = 1;
}
return ans;
}
