#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int NMAX = 2e5 + 1 , LOG = 19;
int T = 0 , ri[NMAX] , rd[NMAX] , ini[NMAX] , outi[NMAX] , ind[NMAX] , outd[NMAX] , t[4 * NMAX] , p[NMAX][2] , up[2][NMAX][LOG];
vector<int> ord = {0};
vector<vector<int>> g(NMAX) , gi(NMAX) , gd(NMAX);
vector<vector<vector<int>>> queries(NMAX);
void update(int u , int l , int r , int pos , int x){
if(l == r){
t[u] = x;
return;
}
int m = (l + r) / 2;
if(pos <= m){
update(u * 2 , l , m , pos , x);
}else{
update(u * 2 + 1 , m + 1 , r , pos , x);
}
t[u] = max(t[u * 2] , t[u * 2 + 1]);
}
int get(int u , int l , int r , int L , int R){
if(l > r || r < L || l > R){
return 0;
}
if(L <= l && r <= R){
return t[u];
}
int m = (l + r) / 2;
return max(get(u * 2 , l , m , L , R) , get(u * 2 + 1 , m + 1 , r , L , R));
}
int find(int u , int type){
return p[u][type] == u ? p[u][type] : p[u][type] = find(p[u][type] , type);
}
void unite(int u , int v , int type){
int root_u = find(u , type) , root_v = find(v , type);
if(root_u != root_v){
p[root_v][type] = root_u;
type == 0 ? ri[root_v] = u : rd[root_v] = u;
}
}
void dfsi(int u){
ini[u] = ++T;
for(int x : gi[u]){
dfsi(x);
}
outi[u] = T;
}
void dfsd(int u){
ord.push_back(u);
ind[u] = ++T;
for(int x : gd[u]){
dfsd(x);
}
outd[u] = T;
}
int max_up_L(int u , int val){
for(int bit = LOG - 1;bit >= 0;bit--){
if(up[1][u][bit] >= val){
u = up[1][u][bit];
}
}
return u;
}
int max_up_R(int u , int val){
for(int bit = LOG - 1;bit >= 0;bit --){
if(up[0][u][bit] <= val){
u = up[0][u][bit];
}
}
return u;
}
vector<int> check_validity(int N , vector<int> X , vector<int> Y , vector<int> S , vector<int> E , vector<int> L , vector<int> R){
int M = (int)X.size();
for(int i = 0;i < M;i ++){
g[++X[i]].push_back(++Y[i]);
g[Y[i]].push_back(X[i]);
}
for(int i = 1;i <= N;i ++){
for(int x = 0;x < 2;x ++){
p[i][x] = i;
}
ri[i] = rd[i] = i;
}
for(int i = 1;i <= N;i ++){
for(int x : g[i]){
if(x < i){
unite(i , x , 0);
}
}
}
for(int i = N;i >= 1;i --){
for(int x : g[i]){
if(x > i){
unite(i , x , 1);
}
}
}
for(int i = 1;i <= N;i ++){
up[0][i][0] = ri[i];
up[1][i][0] = rd[i];
if(ri[i] != i){
gi[ri[i]].push_back(i);
}
if(rd[i] != i){
gd[rd[i]].push_back(i);
}
}
dfsi(N);
T = 0;
dfsd(1);
for(int bit = 1;bit < LOG;bit ++){
for(int i = 1;i <= N;i ++){
for(int x = 0;x < 2;x ++){
up[x][i][bit] = up[x][up[x][i][bit - 1]][bit - 1];
}
}
}
int Q = (int)S.size();
vector<int> ans(Q);
for(int i = 0;i < Q;i ++){
int root_S = max_up_L(++S[i] , ++L[i]);
int root_E = max_up_R(++E[i] , ++R[i]);
queries[outd[root_S]].push_back({ind[root_S] , ini[root_E] , outi[root_E] , i});
}
for(int i = 1;i <= N;i ++){
update(1 , 1 , N , ini[ord[i]] , i);
for(auto x : queries[i]){
ans[x[3]] = get(1 , 1 , N , x[1] , x[2]) >= x[0];
}
}
return ans;
}
