#include "werewolf.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef vector <int> vec;
const int INF = 1e9;
int n,m,Q,uni[200005];
vector <int> v[200005],tvn[200005],tv1[200005];
int p1[200005][18],pn[200005][18];
int in1[200005],inn[200005],out1[200005],outn[200005],co;
int bu[200005];
vector <int> t[800005];
int Find(int x) {return (x == uni[x] ? x : uni[x] = Find(uni[x]));}
void dfs_mark1(int x) {
in1[x] = ++co;
for(int i : tv1[x]) dfs_mark1(i);
out1[x] = co;
}
void dfs_markn(int x) {
inn[x] = ++co;
for(int i : tvn[x]) dfs_markn(i);
outn[x] = co;
}
void build(int x,int l,int r) {
if(l == r) {
t[x].push_back(bu[l]);
return;
}
int mid = (l + r) >> 1;
build(x*2,l,mid), build(x*2+1,mid+1,r);
for(int i : t[x*2]) t[x].push_back(i);
for(int i : t[x*2+1]) t[x].push_back(i);
sort(t[x].begin(),t[x].end());
}
int query(int x,int l,int r,int rl,int rr,int ql,int qr) {
if(rl <= l&&r <= rr) {
int it1 = upper_bound(t[x].begin(),t[x].end(),qr)-t[x].begin()-1, it2 = lower_bound(t[x].begin(),t[x].end(),ql)-t[x].begin()-1;
return (it1-it2 > 0);
}
if(rl > r||l > rr) return 0;
int mid = (l + r) >> 1;
return (query(x*2,l,mid,rl,rr,ql,qr)||query(x*2+1,mid+1,r,rl,rr,ql,qr));
}
vec check_validity(int N,vec X,vec Y,vec S,vec E,vec L,vec R) {
n = N, m = X.size(), Q = S.size();
for(int i = 0;i < m;i++) {
X[i]++, Y[i]++;
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
for(int i = 0;i < Q;i++) {
S[i]++, E[i]++, L[i]++, R[i]++;
}
pn[n][0] = n, p1[1][0] = 1;
for(int i = 1;i <= n;i++) uni[i] = i;
for(int i = 1;i <= n;i++) {
for(int j : v[i]) {
if(j < i) {
if(Find(j) != i) {
int tmp = Find(j); uni[tmp] = i;
pn[tmp][0] = i, tvn[i].push_back(tmp);
}
}
}
}
for(int i = 1;i <= n;i++) uni[i] = i;
for(int i = n;i >= 1;i--) {
for(int j : v[i]) {
if(j > i) {
if(Find(j) != i) {
int tmp = Find(j); uni[tmp] = i;
p1[tmp][0] = i, tv1[i].push_back(tmp);
}
}
}
}
for(int i = 1;i < 18;i++) {
for(int j = 1;j <= n;j++) {
pn[j][i] = pn[pn[j][i-1]][i-1];
p1[j][i] = p1[p1[j][i-1]][i-1];
}
}
dfs_mark1(1); co = 0;
dfs_markn(n);
for(int i = 1;i <= n;i++) bu[inn[i]] = in1[i];
build(1,1,n);
vec ans;
for(int i = 0;i < Q;i++) {
int l,r,x = E[i],l2,r2;
for(int j = 17;j >= 0;j--) {
if(pn[x][j] <= R[i]) x = pn[x][j];
}
l = inn[x], r = outn[x]; x = S[i];
for(int j = 17;j >= 0;j--) {
if(p1[x][j] >= L[i]) x = p1[x][j];
}
l2 = in1[x], r2 = out1[x];
ans.push_back(query(1,1,n,l,r,l2,r2));
}
return ans;
}
