#include "werewolf.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
const int INF=0x3f3f3f3f;
struct UnionFind{
vector<int>par;
UnionFind(int n){
par=vector<int>(n);
rep(i,n)par[i]=i;
}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
void unite(int x,int y){
x=find(x);y=find(y);
par[y]=x;
}
bool same(int x,int y){
return find(x)==find(y);
}
};
struct Segtree{
int N;
vector<int>dat;
function<int(int,int)>f;
int ini;
Segtree(int n,int ini,function<int(int,int)>f):ini(ini),f(f){
N=1;while(N<n)N<<=1;
dat=vector<int>(2*N,ini);
}
void update(int k,int x){
k+=N;dat[k]=x;
while(k>1){
k>>=1;
dat[k]=f(dat[k*2],dat[k*2+1]);
}
}
int query(int l,int r){
int res=ini;
for(l+=N,r+=N;l<r;l>>=1,r>>=1){
if(l&1)res=f(res,dat[l++]);
if(r&1)res=f(res,dat[--r]);
}
return res;
}
};
vector<int>G[300000];
int pos[300000];
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=X.size();
int Q=S.size();
if(N<=3000&&M<=6000&&Q<=3000){
vector<int>ans;
rep(i,Q){
UnionFind uf1(N),uf2(N);
rep(j,M){
if(X[j]>=L[i]&&Y[j]>=L[i])uf1.unite(X[j],Y[j]);
if(X[j]<=R[i]&&Y[j]<=R[i])uf2.unite(X[j],Y[j]);
}
bool ok=false;
rep(j,N){
if(uf1.same(S[i],j)&&uf2.same(E[i],j)){
ok=true;break;
}
}
ans.push_back(ok);
}
return ans;
}
rep(i,M){
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
int s=-1;
rep(i,N){
if(G[i].size()==1){
s=i;break;
}
}
vector<int>vs;
memset(pos,-1,sizeof(pos));
rep(i,N){
vs.push_back(s);
pos[s]=i;
for(int u:G[s]){
if(pos[u]==-1){
s=u;
}
}
}
Segtree seg1(N,INF,[](int a,int b){return min(a,b);});
Segtree seg2(N,0,[](int a,int b){return max(a,b);});
rep(i,N){
seg1.update(i,vs[i]);
seg2.update(i,vs[i]);
}
vector<int>ans;
rep(i,Q){
int s=pos[S[i]],e=pos[E[i]];
if(s<e){
int ok1=s,ng1=N;
while(ng1-ok1>1){
int t=(ok1+ng1)/2;
if(seg1.query(s,t+1)>=L[i])ok1=t;
else ng1=t;
}
int ok2=e,ng2=-1;
while(ok2-ng2>1){
int t=(ok2+ng2)/2;
if(seg2.query(t,e+1)<=R[i])ok2=t;
else ng2=t;
}
ans.push_back(ok2<=ok1);
}
else{
int ok1=s,ng1=-1;
while(ok1-ng1>1){
int t=(ok1+ng1)/2;
if(seg1.query(t,s+1)>=L[i])ok1=t;
else ng1=t;
}
int ok2=e,ng2=N;
while(ng2-ok2>1){
int t=(ok2+ng2)/2;
if(seg2.query(e,t+1)<=R[i])ok2=t;
else ng2=t;
}
ans.push_back(ok1<=ok2);
}
}
return ans;
}
