#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
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 = X.size();
vector<int> g1[N+N-1], g2[N+N-1];
int d1[N+N-1], d2[N+N-1];
int par[N+N-1], val1[N+N-1], val2[N+N-1];
int pos1[N+N-1], pos2[N+N-1], id1 = 0, id2 = 0;
#define fi first
#define se second
using ii = pair<int, int>;
vector<vector<ii> > f(20, vector<ii>(4*N)), g(20, vector<ii>(4*N));
function<int(int)> find_set = [&](int v) {
return par[v] == v ? v : par[v] = find_set(par[v]);
};
fill(val1, val1 + N + N - 1, N);
fill(val2, val2 + N + N - 1, 0);
struct edge {
int u, v, l;
edge() {}
edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {}
} edges[M];
for (int i = 0; i < M; i++) edges[i] = edge(X[i], Y[i], min(X[i], Y[i]));
sort(edges, edges + M, [&](edge x, edge y) {
return x.l > y.l;
});
int root1 = N, root2 = N;
iota(par, par + N + N - 1, 0);
for (int i = 0; i < M; i++) {
auto [u, v, l] = edges[i];
u = find_set(u); v = find_set(v);
if (u == v) continue;
g1[root1].emplace_back(u);
g1[root1].emplace_back(v);
val1[root1] = l;
par[u] = root1;
par[v] = root1;
++root1;
}
d1[root1-1] = 0;
function<void(int)> dfs1 = [&](int u) {
f[0][++id1] = {d1[u], u};
pos1[u] = id1;
for (int v : g1[u]) {
d1[v] = d1[u] + 1;
dfs1(v);
f[0][++id1] = {d1[u], u};
}
};
dfs1(root1-1);
for (int i = 1; (1<<i) <= id1; i++) for (int j = 1; j + (1<<i) - 1 <= id1; j++) f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);
for (int i = 0; i < M; i++) edges[i] = edge(X[i], Y[i], max(X[i], Y[i]));
sort(edges, edges + M, [&](edge x, edge y) {
return x.l < y.l;
});
iota(par, par + N + N - 1, 0);
for (int i = 0; i < M; i++) {
auto [u, v, l] = edges[i];
u = find_set(u); v = find_set(v);
if (u == v) continue;
g2[root2].emplace_back(u);
g2[root2].emplace_back(v);
val2[root2] = l;
par[u] = root2;
par[v] = root2;
++root2;
}
d2[root2-1] = 0;
function<void(int)> dfs2 = [&](int u) {
g[0][++id2] = {d2[u], u};
pos2[u] = id2;
for (int v : g2[u]) {
d2[v] = d2[u] + 1;
dfs2(v);
g[0][++id2] = {d2[u], u};
}
};
dfs2(root2-1);
for (int i = 1; (1<<i) <= id2; i++) for (int j = 1; j + (1<<i) - 1 <= id2; j++) g[i][j] = min(g[i-1][j], g[i-1][j+(1<<(i-1))]);
function<int(int, int)> LCA1 = [&](int u, int v) {
u = pos1[u]; v = pos1[v];
if (u > v) swap(u, v);
int k = __lg(v-u+1);
return min(f[k][u], f[k][v-(1<<k)+1]).se;
};
function<int(int, int)> LCA2 = [&](int u, int v) {
u = pos2[u]; v = pos2[v];
if (u > v) swap(u, v);
int k = __lg(v-u+1);
return min(g[k][u], g[k][v-(1<<k)+1]).se;
};
int st[21*N+5], Lef[21*N+5], Rig[21*N+5];
int c1[N+1], c2[N+1];
iota(c1 + 1, c1 + N + 1, 0);
iota(c2 + 1, c2 + N + 1, 0);
sort(c1 + 1, c1 + N + 1, [&](int x, int y) {
return pos1[x] < pos1[y];
});
sort(c2 + 1, c2 + N + 1, [&](int x, int y) {
return pos2[x] < pos2[y];
});
int rem[N], root[N+1], nho[N];
for (int i = 1; i <= N; i++) nho[c1[i]] = i;
for (int i = 1; i <= N; i++) rem[c2[i]] = i;
int nt = 0;
function<int(int, int)> build = [&](int lo, int hi) {
if (lo == hi) {
st[++nt] = 0;
return nt;
}
int cur = ++nt, mid = (lo + hi) >> 1;
Lef[cur] = build(lo, mid);
Rig[cur] = build(mid+1, hi);
st[cur] = 0;
return cur;
};
root[0] = build(1, N);
function<int(int, int, int, int)> upd = [&](int u, int oldver, int lo, int hi) {
if (lo == hi) {
st[++nt] = st[oldver] + 1;
return nt;
}
int cur = ++nt, mid = (lo + hi) >> 1;
if (u <= mid) {
Lef[cur] = upd(u, Lef[oldver], lo, mid);
Rig[cur] = Rig[oldver];
} else {
Lef[cur] = Lef[oldver];
Rig[cur] = upd(u, Rig[oldver], mid+1, hi);
}
st[cur] = st[Lef[cur]] + st[Rig[cur]];
return cur;
};
function<int(int, int, int, int, int)> get = [&](int u, int v, int r, int lo, int hi) {
if (u > hi || v < lo) return 0;
if (u <= lo && hi <= v) return st[r];
int mid = (lo + hi) >> 1;
return get(u, v, Lef[r], lo, mid) + get(u, v, Rig[r], mid+1, hi);
};
for (int i = 1; i <= N; i++) {
int u = c1[i];
root[i] = upd(rem[u], root[i-1], 1, N);
}
int Q = S.size();
vector<int> ans;
function<void(int)> solve = [&](int idx) {
int s = S[idx], e = E[idx], l = L[idx], r = R[idx];
int Leftup, Rightup, Leftdown, Rightdown, lo, hi, cur;
cur = nho[s];
lo = cur; hi = N+1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (val1[LCA1(s, c1[mid])] >= l) lo = mid;
else hi = mid;
}
Rightup = lo;
lo = 0; hi = cur;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (val1[LCA1(s, c1[mid])] >= l) hi = mid;
else lo = mid;
}
Leftup = hi;
cur = rem[e];
lo = cur; hi = N+1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (val2[LCA2(e, c2[mid])] <= r) lo = mid;
else hi = mid;
}
Rightdown = lo;
lo = 0; hi = cur;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (val2[LCA2(e, c2[mid])] <= r) hi = mid;
else lo = mid;
}
Leftdown = hi;
bool flag = ((get(Leftdown, Rightdown, root[Rightup], 1, N) - get(Leftdown, Rightdown, root[Leftup-1], 1, N)) > 0);
ans.emplace_back(int(flag));
};
for (int o = 0; o < Q; o++) solve(o);
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
