#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
const int mxN = 2e5+5;
const int lgN = 17;
const int mxM = 4e5+5;
const int mxQ = 2e5+5;
int N, M, Q;
struct Edge { int X, Y, W; } edge[mxM];
struct SegmentTree {
vector<int> d[8*mxN];
int n;
SegmentTree(int n): n(n) {}
void update(int x, int v, int s, int e, int p) {
if (s == e) {
d[p].push_back(v);
} else {
int m = (s+e)/2;
if (x <= m) update(x,v,s,m,p*2);
else update(x,v,m+1,e,p*2+1);
}
}
inline void update(int x, int v) { update(x,v,0,n-1,1); }
void build(int s, int e, int p) {
if (s != e) {
int m = (s+e)/2;
build(s,m,p*2);
build(m+1,e,p*2+1);
vector<int>& a = d[2*p], b = d[2*p+1];
for (int i = 0, j = 0; i < SZ(a) || j < SZ(b); ) {
if (i < SZ(a) && (j == SZ(b) || a[i] < b[j])) d[p].push_back(a[i++]);
else d[p].push_back(b[j++]);
}
}
}
inline void build() { build(0,n-1,1); }
int query(int x, int y, int u, int v, int s, int e, int p) {
if (s == x && e == y) {
return lower_bound(ALL(d[p]),v+1) - lower_bound(ALL(d[p]),u);
} else {
int m = (s+e)/2;
if (y <= m) return query(x,y,u,v,s,m,p*2);
if (x > m) return query(x,y,u,v,m+1,e,p*2+1);
return query(x,m,u,v,s,m,p*2) + query(m+1,y,u,v,m+1,e,p*2+1);
}
}
inline int query(int x, int y, int u, int v) { return query(x,y,u,v,0,n-1,1); }
} *ST;
struct KruskalTree {
static const int mxV = 2*mxN;
int pa[mxV], v[mxV];
vector<int> al[mxV];
int cnt, fa[mxV][lgN+1], pre[mxV], pst[mxV], dfsT;
KruskalTree(int n) {
FOR(i,0,n-1){
pa[i] = i;
v[i] = -1;
}
cnt = n;
memset(fa,-1,sizeof fa);
}
int finds(int i) { return (pa[i] == i) ? i : (pa[i] = finds(pa[i])); }
bool unions(int i, int j, int w) {
int x = finds(i), y = finds(j);
if (x != y) {
pa[cnt] = cnt;
v[cnt] = w;
al[cnt].push_back(x);
al[cnt].push_back(y);
fa[x][0] = cnt;
fa[y][0] = cnt;
pa[x] = pa[y] = cnt;
++cnt;
return true;
} return false;
}
void dfs(int u) {
pre[u] = dfsT++;
FOR(k,1,lgN){
if (fa[u][k-1] == -1) fa[u][k] = -1;
else fa[u][k] = fa[fa[u][k-1]][k-1];
}
for (int v : al[u]) { dfs(v); }
pst[u] = dfsT-1;
//TRACE(u _ v[u] _ pre[u] _ pst[u]);
}
void init() {
dfsT = 0;
dfs(cnt-1);
}
int findFaGE(int u, int val) {
RFOR(k,lgN,0){
if (fa[u][k] != -1 && v[fa[u][k]] >= val) u = fa[u][k];
}
return u;
}
} *KT1, *KT2;
std::vector<int> check_validity(int _N, 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 = _N, M = SZ(X), Q = SZ(S);
FOR(i,0,M-1){
edge[i] = (Edge){ X[i], Y[i], min(X[i],Y[i]) };
}
sort(edge,edge+M,[](Edge a, Edge b){
if (a.W == b.W) return (a.X == b.X ? a.Y < b.Y : a.X < b.X);
return a.W > b.W;
});
KT1 = new KruskalTree(N);
FOR(i,0,M-1){
KT1->unions(edge[i].X,edge[i].Y,edge[i].W);
}
KT1->init();
FOR(i,0,M-1) edge[i].W = max(edge[i].X,edge[i].Y);
sort(edge,edge+M,[](Edge a, Edge b){
if (a.W == b.W) return (a.X == b.X ? a.Y < b.Y : a.X < b.X);
return a.W < b.W;
});
KT2 = new KruskalTree(N);
FOR(i,0,M-1){
KT2->unions(edge[i].X,edge[i].Y,-edge[i].W);
}
KT2->init();
ST = new SegmentTree(2*N);
FOR(i,0,N-1){
//TRACE(i _ KT1->pre[i] _ KT2->pre[i]);
ST->update(KT1->pre[i],KT2->pre[i]);
}
ST->build();
vector<int> ans(Q);
FOR(i,0,Q-1){
int sp = KT1->findFaGE(S[i],L[i]);
int ep = KT2->findFaGE(E[i],-R[i]);
//TRACE(sp _ KT1->pre[sp] _ KT1->pst[sp] _ ep _ KT2->pre[ep] _ KT2->pst[ep]);
ans[i] = ST->query(KT1->pre[sp],KT1->pst[sp],KT2->pre[ep],KT2->pst[ep]) > 0;
}
return ans;
}
