#include <bits/stdc++.h>
#include "werewolf.h"
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()
using namespace std;
int n,m,q,timer,root[2];
vector<vector<int>> g;
vector<vector<pair<int,int>>> tr[2];
vector<int> dsu,sz, in[2], out[2];
vector<pair<int,int>> par[2],trav[2];
vector<int> bit;
void upd(int x, int v){
for(;x<=n;x+=x&-x) bit[x]+=v;
}
int sum(int x){
int ret=0;
for(;x>0;x-=x&-x) ret+=bit[x];
return ret;
}
int getp(int x){
return dsu[x]==x?x:dsu[x]=getp(dsu[x]);
}
void connect(int u, int v, int t){
u=getp(u), v=getp(v);
if(u==v) return;
if(sz[u]<sz[v]) swap(u,v);
dsu[v]=u;
sz[u]+=sz[v];
par[t][v]={timer,u};
tr[t][u].pb({timer,v});
}
bool connected(int u, int v){
return getp(u)==getp(v);
}
void dfs(int u, int t){
in[t][u]=sz(trav[t]);
trav[t].pb({u,in[t][u]});
for(auto v:tr[t][u]){
dfs(v.y,t);
}
out[t][u]=sz(trav[t])-1;
}
pair<int,int> getblock(int u, int L, int t){
while(par[t][u].x<=L) u = par[t][u].y;
int l=-1, r=sz(tr[t][u])-1;
while(l<r){
int md=(l+r+1)/2;
if(tr[t][u][md].x>L) r=md-1;
else l=md;
}
if(l==-1) return {in[t][u],in[t][u]};
return {in[t][u],out[t][tr[t][u][l].y]};
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
n=N;
m=sz(X);
q=sz(S);
g.resize(n), dsu.resize(n), sz.resize(n), tr[0].resize(n), tr[1].resize(n), par[0].resize(n), par[1].resize(n);
in[0].resize(n), in[1].resize(n), out[0].resize(n), out[1].resize(n), bit.resize(n+1);
for(int i=0;i<n;i++) dsu[i]=i, sz[i]=1, par[0][i]=par[1][i]={(int)1e9,-1};
for(int i=0;i<m;i++){
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
for(int i=0;i<n;i++) sort(all(g[i]));
for(int i=0;i<n;i++){
timer=i;
for(int u:g[i]){
if(i<u) continue;
connect(i,u,0);
}
}
root[0]=getp(0);
dfs(root[0],0);
for(int i=0;i<n;i++) dsu[i]=i, sz[i]=1;
for(int i=n-1;i>=0;i--){
timer=n-1-i;
for(int u:g[i]){
if(i<u) connect(i,u,1);
}
}
root[1]=getp(0);
dfs(root[1],1);
sort(all(trav[0]));
sort(all(trav[1]));
for(int i=0;i<n;i++) trav[1][i].x=trav[0][i].y, swap(trav[1][i].x,trav[1][i].y);
sort(all(trav[1]));
vector<pair<pair<int,int>,int>> queriesL[n], queriesR[n];
vector<int> cnt(q);
for(int i=0;i<q;i++){
pair<int,int> p1=getblock(E[i],R[i],0);
pair<int,int> p2=getblock(S[i],n-1-L[i],1);
if(p2.x>0 && p1.x>0) queriesL[p2.x-1].pb({{p1.x-1,i},-1});
if(p1.x>0) queriesL[p2.y].pb({{p1.x-1,i},1});
if(p2.x>0 && p1.y<n-1) queriesR[p2.x-1].pb({{p1.y+1,i},-1});
if(p1.y<n-1) queriesR[p2.y].pb({{p1.y+1,i},1});
cnt[i]=p2.y-p2.x+1;
}
for(int i=0;i<n;i++){
upd(trav[1][i].y+1,1);
for(auto p:queriesL[i]){
cnt[p.x.y]-=sum(p.x.x+1)*p.y;
}
}
for(int i=0;i<=n;i++) bit[i]=0;
for(int i=0;i<n;i++){
upd(trav[1][i].y+1,1);
for(auto p:queriesR[i]){
cnt[p.x.y]-=(sum(n)-sum(p.x.x))*p.y;
}
}
vector<int> ret(q);
for(int i=0;i<q;i++) ret[i]=(bool)(cnt[i]>0);
return ret;
}
