#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
int N, M, Q;
vim V[200010];
struct sler {
int s, l, n, nd;
}sl[200010], er[200010];
struct tree {
int tp, tp1;
vim ch[400010];
int s[400010], e[400010];
void in(int a, int b) {
ch[tp].push_back(a); ch[tp].push_back(b); tp++;
}
void dfs(int now) {
s[now]=e[now]=tp1; tp1++;
for (int i:ch[now]) {
dfs(i);
e[now]=max(e[now], e[i]);
}
}
}tr1, tr2;
struct Query {
int x1, x2, y1, y2, n, ans;
}Qu[200010];
int par[200010], im[200010], dep[200010];
void Un1(int a, int b) {
while (par[a]!=-1) a=par[a];
while (par[b]!=-1) b=par[b];
if (a==b) return ;
if (dep[a]<dep[b]) swap(a, b);
par[b]=a, dep[a]=max(dep[a], dep[b]+1);
tr1.in(im[a], im[b]);
im[a]=tr1.tp-1;
}
void f1() {
tr1.tp=N, tr1.tp1=0;
for (int i=0; i<N; i++) par[i]=-1, im[i]=i, dep[i]=0;
for (int i=N-1, t=0; i>=0; i--) {
for (int j:V[i]) {
if (j>i) Un1(i, j);
}
for (; t<Q&&sl[t].l>=i; t++) {
int l=sl[t].s; while(par[l]!=-1) l=par[l];
sl[t].nd=im[l];
}
}
tr1.dfs(tr1.tp-1);
}
void Un2(int a, int b) {
while (par[a]!=-1) a=par[a];
while (par[b]!=-1) b=par[b];
if (a==b) return ;
if (dep[a]<dep[b]) swap(a, b);
par[b]=a, dep[a]=max(dep[a], dep[b]+1);
tr2.in(im[a], im[b]);
im[a]=tr2.tp-1;
}
void f2() {
tr2.tp=N, tr2.tp1=0;
for (int i=0; i<N; i++) par[i]=-1, im[i]=i, dep[i]=0;
for (int i=0, t=0; i<N; i++) {
for (int j:V[i]) {
if (j<i) Un2(i, j);
}
for (; t<Q&&er[t].l<=i; t++) {
int l=er[t].s; while(par[l]!=-1) l=par[l];
er[t].nd=im[l];
}
}
tr2.dfs(tr2.tp-1);
}
pii ar[200010];
int seg[(1<<20)];
vim check_validity(int N_, vim X, vim Y, vim S, vim E, vim L, vim R) {
N=N_; M=X.size(); Q=S.size();
for (int i=0; i<M; i++) {
V[X[i]].push_back(Y[i]);
V[Y[i]].push_back(X[i]);
}
for (int i=0; i<Q; i++) {
sl[i]={S[i], L[i], i, 0};
er[i]={E[i], R[i], i, 0};
}
sort(sl, sl+Q, [](sler a, sler b){return a.l>b.l;});
sort(er, er+Q, [](sler a, sler b){return a.l<b.l;});
f1(); f2();
sort(sl, sl+Q, [](sler a, sler b){return a.n<b.n;});
sort(er, er+Q, [](sler a, sler b){return a.n<b.n;});
for (int i=0; i<N; i++) {
ar[i]={tr1.s[i], tr2.s[i]};
assert(tr1.s[i]==tr1.e[i]&&tr2.s[i]==tr2.e[i]);
}
sort(ar, ar+N);
for (int i=0; i<Q; i++) {
int nd1=sl[i].nd, nd2=er[i].nd;
Qu[i]={tr1.s[nd1], tr1.e[nd1], tr2.s[nd2], tr2.e[nd2], i, 0};
}
sort(Qu, Qu+Q, [](Query a, Query b){return a.x2<b.x2;});
int mx=0;
for (int i=0, j=0; i<Q; i++) {
for (; j<N && ar[j].fi<=Qu[i].x2; j++) for (int k=(1<<19)+ar[j].se; k; k/=2) seg[k]=max(seg[k], ar[j].fi);
mx=0;
for (int k=(1<<19)+Qu[i].y1, l=(1<<19)+Qu[i].y2; k<=l; k/=2, l/=2) {
if (k%2) mx=max(mx, seg[k++]);
if (l%2==0) mx=max(mx, seg[l--]);
}
if (mx>=Qu[i].x1) Qu[i].ans=1;
else Qu[i].ans=0;
}
sort(Qu, Qu+Q, [](Query a, Query b){return a.n<b.n;});
vim ans;
for (int i=0; i<Q; i++) ans.push_back(Qu[i].ans);
return ans;
}
