#include "werewolf.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
struct tree {
vector <int> F[200020];
int lv[200020], rv[200020], cs = 0;
int up[200020][18];
void addE(int x, int y) { // x <- y
F[x].pb(y);
}
void dfs(int x) {
lv[x] = ++cs;
for(int e : F[x]) {
up[e][0] = x;
for(int i=1;i<18;i++) {
up[e][i] = up[ up[e][i-1] ][i-1];
}
dfs(e);
}
rv[x] = cs;
}
pii get_seg_g(int x, int l) {
for(int i=17;i>=0;i--) {
if(up[x][i] && up[x][i] >= l) x = up[x][i];
}
return pii(lv[x], rv[x]);
}
pii get_seg_l(int x, int r) {
for(int i=17;i>=0;i--) {
if(up[x][i] && up[x][i] <= r) x = up[x][i];
}
return pii(lv[x], rv[x]);
}
} T[2];
int pp[200020]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
int val[200020];
vector <int> EE[200010];
int N;
vector <t3> pquery[200020];
int TT[200020];
int cnt[200020];
void pre_query(int idx, int S, int E, int L, int R) {
pii p1 = T[0].get_seg_l(E, R);
pii p2 = T[1].get_seg_g(S, L);
pquery[p1.Se].pb(t3(p2.Se, idx, 1));
pquery[p1.Se].pb(t3(p2.Fi-1, idx, -1));
pquery[p1.Fi-1].pb(t3(p2.Se, idx, -1));
pquery[p1.Fi-1].pb(t3(p2.Fi-1, idx, 1));
}
std::vector<int> check_validity(int nn, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
N = nn;
int M = szz(X);
for(int i=0;i<M;i++) {
int x = X[i] + 1, y = Y[i] + 1;
EE[x].pb(y);
EE[y].pb(x);
}
for(int i=1;i<=N;i++) pp[i] = i;
for(int i=1;i<=N;i++) {
for(int e : EE[i]) if(e < i) {
int x = Find(i), y = Find(e);
if(x == y) continue;
pp[y] = x;
T[0].addE(x, y);
}
}
for(int i=1;i<=N;i++) pp[i] = i;
for(int i=N;i;i--) {
for(int e : EE[i]) if(e > i) {
int x = Find(i), y = Find(e);
if(x == y) continue;
pp[y] = x;
T[1].addE(x, y);
}
}
T[0].dfs(N); T[1].dfs(1);
for(int i=1;i<=N;i++) {
val[T[0].lv[i]] = T[1].lv[i];
}
int Q = szz(S);
rep(i, Q) {
++S[i]; ++E[i]; ++L[i]; ++R[i];
pre_query(i, S[i], E[i], L[i], R[i]);
}
for(int i=1;i<=N;i++) {
int x = val[i];
for(int j=x;j<200020;j+=(j&-j)) TT[j]++;
for(t3 e : pquery[i]) {
int y, idx, cc;
tie(y, idx, cc) = e;
int s = 0;
for(int j=y;j;j-=(j&-j)) s += TT[j];
cnt[idx] += cc * s;
}
}
vector <int> A(Q);
rep(i, Q) {
A[i] = cnt[i] > 0 ? 1 : 0;
}
return A;
}
