#include "werewolf.h"
#define pb push_back
#define VI vector<int>
#include<bits/stdc++.h>
using namespace std;
#define MXN 400100
struct node{
int l,r,val,lc,rc;
node():l(0){}
node(int l, int r, int val, int lc, int rc):l(l),r(r),val(val),lc(lc),rc(rc){}
node(int pos):l(pos),r(pos),val(1){}
} t[15*MXN];
int cnt;
int query(int i, int l, int r) {
if(!t[i].val||t[i].l>r||t[i].r<l)return 0;
if(l<=t[i].l&&t[i].r<=r) return t[i].val;
return query(t[i].lc,l,r)+query(t[i].rc,l,r);
}
int mn(int a, int b) {
t[++cnt] = node(t[a].l,t[b].r,t[a].val+t[b].val,a,b);
return cnt;
}
int upd(int i, int pos) {
if(t[i].l==t[i].r) {
t[++cnt] = node(pos);
return cnt;
}
if(pos<t[t[i].rc].l)
return mn(upd(t[i].lc,pos),t[i].rc);
return mn(t[i].lc, upd(t[i].rc, pos));
}
int build(int l, int r){
if(l==r) return t[++cnt]=node(l,l,0,0,0),cnt;
return mn(build(l,l+r>>1),build(l+r+2>>1,r));
}
int order[2][MXN], times[4][MXN], cntx, p[MXN], tb[2][20][MXN], cnty;
int abp(int n) {
return (p[n]==n)?n:(p[n]=abp(p[n]));
}
VI adj[4][MXN];
void dfs1(int n) {
order[0][times[0][n]=++cntx] = n;
for(auto i: adj[0][n])
dfs1(i);
times[2][n] = cntx;
}
void dfs2(int n) {
order[1][times[1][n]=++cntx] = n;
for(auto i: adj[1][n])
dfs2(i);
times[3][n] = cntx;
}
VI rt;
VI check_validity(int N,VI X,VI Y,VI s,VI e,VI l,VI r){
VI ans;
for(int i = 0; i < X.size(); i++) {
if(X[i] < Y[i])
adj[2][X[i]].pb(Y[i]),
adj[3][Y[i]].pb(X[i]);
else
adj[3][X[i]].pb(Y[i]),
adj[2][Y[i]].pb(X[i]);
}
iota(p, p+MXN, 0);
for(int i = N; i--;) {
for(auto j: adj[2][i]) {
if(abp(j)!=i) {
adj[0][i].pb(p[j]);
tb[0][0][p[j]] = i;
p[p[j]]=i;
}
}
}
iota(p, p+MXN, 0);
for(int i = 0; i < N; i++) {
for(auto j: adj[3][i]) {
if(abp(j)!=i) {
adj[1][i].pb(p[j]);
tb[1][0][p[j]] = i;
p[p[j]]=i;
}
}
}
tb[1][0][N-1] = tb[1][0][N] = N;
for(int i = 1; i < 20; i++)
for(int j = 0; j < 2*N; j++)
tb[0][i][j] = tb[0][i-1][tb[0][i-1][j]], tb[1][i][j] = tb[1][i-1][tb[1][i-1][j]];
dfs1(0);
cntx=0;
dfs2(N-1);
rt.pb(build(1,N));
for(int i = 1; i <= N; i++) {
rt.pb(upd(rt.back(), times[1][order[0][i]]));
}
for(int i = 0; i < s.size(); i++) {
int a = s[i], b = e[i], c = l[i], d = r[i];
for(int i = 20; i--;) {
if(tb[0][i][a]>=c)
a = tb[0][i][a];
if(tb[1][i][b]<=d)
b = tb[1][i][b];
}
int A,B,C,D;
A = times[0][a];
B = times[2][a];
C = times[1][b];
D = times[3][b];
ans.pb((bool)(query(rt[B], C, D) - query(rt[A-1],C,D)));
}
return ans;
}
