#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn = 6e4+10;
int n;
struct Edge
{
int u, v, w;
} edge[2][maxn];
struct DSU
{
int pai[maxn];
void init(void)
{
for (int i = 1; i < maxn; i++)
pai[i] = i;
}
int Find(int x)
{
if (pai[x] == x) return x;
return pai[x] = Find(pai[x]);
}
void Join(int x, int y)
{
x = Find(x), y = Find(y);
if (x == y) return;
pai[y] = x;
}
} dsu;
struct SegmentTree
{
int tree[4*maxn];
void upd(int node, int l, int r, int pos, int v)
{
if (l == r)
{
tree[node] = max(tree[node], v);
return;
}
int mid = (l+r)>>1;
if (pos <= mid) upd(2*node, l, mid, pos, v);
else upd(2*node+1, mid+1, r, pos, v);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
int query(int node, int l, int r, int a, int b)
{
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node];
int mid = (l+r)>>1;
return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
}
} seg;
struct Event
{
int x1, x2, y1, y2, t, ind;
bool operator <(const Event &o)
{
if (o.x2 == x2) return t < o.t;
return x2 < o.x2;
}
} event[maxn];
int val[2][maxn];
int st[2][maxn], en[2][maxn], tt;
int tab[2][maxn][20];
int ans[maxn];
vector<int> grafo[2][maxn];
void dfs(int u, int p, int q)
{
st[q][u] = ++tt;
for (auto v: grafo[q][u])
{
if (v != p)
{
tab[q][v][0] = u;
dfs(v, u, q);
}
}
en[q][u] = tt;
}
void build_tab(int q)
{
for (int j = 1; j < 20; j++)
for (int i = 1; i < maxn; i++)
tab[q][i][j] = tab[q][tab[q][i][j-1]][j-1];
}
int get_menor(int u, int k)
{
for (int i = 19; i >= 0; i--)
if (val[0][tab[0][u][i]] >= k)
u = tab[0][u][i];
return u;
}
int get_maior(int u, int k)
{
for (int i = 19; i >= 0; i--)
if (tab[1][u][i] && val[1][tab[1][u][i]] <= k)
u = tab[1][u][i];
return u;
}
void build(int q, int m)
{
dsu.init();
int ind = n;
for (int i = 1; i <= m; i++)
{
int u = dsu.Find(edge[q][i].u), v = dsu.Find(edge[q][i].v), w = edge[q][i].w;
if (u != v)
{
++ind;
val[q][ind] = w;
dsu.Join(ind, u); dsu.Join(ind, v);
grafo[q][ind].push_back(u); grafo[q][u].push_back(ind);
grafo[q][ind].push_back(v); grafo[q][v].push_back(ind);
}
}
tt = 0;
dfs(dsu.Find(1), 0, q);
build_tab(q);
}
void do_sweep(int q)
{
sort(event+1, event+q+1);
for (int i = 1; i <= q; i++)
{
auto E = event[i];
if (E.t == 0) seg.upd(1, 1, maxn-1, E.y1, E.x1);
else ans[E.ind] = (seg.query(1, 1, maxn-1, E.y1, E.y2) >= E.x1 ? 1 : 0);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R)
{
n = N;
int m = 0;
for (int i = 0; i < X.size(); i++)
{
edge[0][++m] = {X[i]+1, Y[i]+1, min(X[i]+1, Y[i]+1)};
edge[1][m] = {X[i]+1, Y[i]+1, max(X[i]+1, Y[i]+1)};
}
sort(edge[0]+1, edge[0]+m+1, [&] (Edge a, Edge b) {return a.w > b.w;});
build(0, m);
sort(edge[1]+1, edge[1]+m+1, [&] (Edge a, Edge b) {return a.w < b.w;});
build(1, m);
int queries = 0;
for (int i = 0; i < S.size(); i++)
{
int s = S[i]+1, e = E[i]+1, l = L[i]+1, r = R[i]+1;
int u = get_menor(s, l);
int v = get_maior(e, r);
event[++queries] = {st[0][u], en[0][u], st[1][v], en[1][v], 1, i+1};
}
for (int i = 1; i <= n; i++)
event[++queries] = {st[0][i], st[0][i], st[1][i], st[1][i], 0, 0};
do_sweep(queries);
vector<int> final;
for (int i = 1; i <= S.size(); i++)
final.push_back(ans[i]);
return final;
}
