#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll S = (1 << 20);
class MergeSortTree{
public:
ll query(ll l, ll r, ll mn, ll mx) {return query(1, 1, S / 2, l, r, mn, mx);}
void init(){
for(int i = S / 2 - 1; i >= 1; i--){
vector<ll> &L = T[i * 2], &R = T[i * 2 + 1];
T[i].resize(L.size() + R.size());
merge(L.begin(), L.end(), R.begin(), R.end(), T[i].begin());
}
}
void push(ll k, ll v){
T[k + S / 2 - 1].push_back(v);
}
bool query(ll node, ll s, ll e, ll l, ll r, ll mn, ll mx){
if(e < l || s > r) return 0;
if(l <= s && e <= r){
ll I = lower_bound(T[node].begin(), T[node].end(), mn) - T[node].begin();
return (I < T[node].size() && T[node][I] <= mx);
}
ll m = (s + e) / 2, lch = node * 2, rch = node * 2 + 1;
ll x = query(lch, s, m, l, r, mn, mx);
ll y = query(rch, m + 1, e, l, r, mn, mx);
return x || y;
}
private:
vector<ll> T[2 * S];
};
struct UnionFind{
ll p[200005];
UnionFind() {Reset();}
void Reset() {fill(p, p + 200005, -1);}
ll Find(ll n) {return (p[n] < 0 ? n : p[n] = Find(p[n]));}
void Union(ll a, ll b) {a = Find(a), b = Find(b); if(a == b) return; p[a] += p[b]; p[b] = a; }
bool Same(ll a, ll b) {return Find(a) == Find(b);}
};
UnionFind uf;
ll N, M, Q;
vector<ll> G[200005];
ll P1[200005][22];
ll P2[200005][22];
vector<ll> C1[200005];
vector<ll> C2[200005];
ll in1[200005];
ll in2[200005];
ll out1[200005];
ll out2[200005];
ll num1 = 0, num2 = 0;
void ETT1(ll u){
in1[u] = ++num1;
for(auto v : C1[u]) ETT1(v);
out1[u] = num1;
}
void ETT2(ll u){
in2[u] = ++num2;
for(auto v : C2[u]) ETT2(v);
out2[u] = num2;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
M = X.size(), Q = S.size();
vector<int> A(Q);
for(int i = 0; i < M; i++){
ll u = ++X[i], v = ++Y[i];
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = 1; i <= N; i++){
for(auto j : G[i]){
if(j > i || uf.Same(i, j)) continue;
ll k = uf.Find(j);
uf.Union(i, k);
P1[k][0] = i;
C1[i].push_back(k);
}
}
P1[N][0] = N;
for(int j = 1; j < 22; j++){
for(int i = 1; i <= N; i++){
P1[i][j] = P1[P1[i][j - 1]][j - 1];
}
}
ETT1(N);
uf.Reset();
for(int i = N; i >= 1; i--){
for(auto j : G[i]){
if(j < i || uf.Same(i, j)) continue;
ll k = uf.Find(j);
uf.Union(i, k);
P2[k][0] = i;
C2[i].push_back(k);
}
}
P2[1][0] = 1;
for(int j = 1; j < 22; j++){
for(int i = 1; i <= N; i++){
P2[i][j] = P2[P2[i][j - 1]][j - 1];
}
}
ETT2(1);
MergeSortTree SRT;
for(int i = 1; i <= N; i++){
SRT.push(in1[i], in2[i]);
}
SRT.init();
for(int i = 0; i < Q; i++){
S[i]++, E[i]++, L[i]++, R[i]++;
ll u = S[i], v = E[i];
for(int j = 21; j >= 0; j--){
if(P2[u][j] >= L[i]){
u = P2[u][j];
}
}
for(int j = 21; j >= 0; j--){
if(P1[v][j] <= R[i]){
v = P1[v][j];
}
}
A[i] = SRT.query(in1[v], out1[v], in2[u], out2[u]);
}
return A;
}
