#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int N = 6e6 + 200;
ve<int> gr1[N]; int p1[N], w1 = 0;
inline int par1(int v) { if (p1[v] == v) { return v; } return (p1[v] = par1(p1[v])); }
inline void add1(int a, int b) {
a = par1(a), b = par1(b);
if (a == b) return;
int c = w1++;
p1[a] = p1[b] = p1[c] = c;
gr1[c].pb(a);
if (a ^ b) gr1[c].pb(b);
} int ti1 = 0;
int in1[N], out1[N];
inline void dfs1(int v) {
in1[v] = ti1++;
for (auto &to : gr1[v]) dfs1(to);
out1[v] = ti1 - 1;
}
ve<int> gr2[N]; int p2[N], w2 = 0;
inline int par2(int v) { if (p2[v] == v) { return v; } return (p2[v] = par2(p2[v])); }
inline void add2(int a, int b) {
a = par2(a), b = par2(b);
if (a == b) return;
int c = w2++;
p2[a] = p2[b] = p2[c] = c;
gr2[c].pb(a);
if (a ^ b) gr2[c].pb(b);
} int ti2 = 0;
int in2[N], out2[N];
inline void dfs2(int v) {
in2[v] = ti2++;
for (auto &to : gr2[v]) dfs2(to);
out2[v] = ti2 - 1;
}
struct node {
node *l = nullptr;
node *r = nullptr;
int s = 0;
node() {}
node(int x) : s(x) {}
};
inline void upd(node *v, int vl, int vr, int pos, int x) {
if (vl == vr) return void(v->s += x);
int m = vl + vr >> 1;
if (pos <= m) {
if (!v->l) v->l = new node();
upd(v->l, vl, m, pos, x);
}
else {
if (!v->r) v->r = new node();
upd(v->r, m + 1, vr, pos, x);
}
v->s = 0;
if (v->l) v->s += v->l->s;
if (v->r) v->s += v->r->s;
}
inline int get(node *v, int vl, int vr, int l, int r) {
if (!v || l > r) return 0;
else if (vl == l && vr == r) return v->s;
int m = vl + vr >> 1;
int a = get(v->l, vl, m, l, min(r, m));
int b = get(v->r, m + 1, vr, max(l, m + 1), r);
return a + b;
}
node *t[4 * N]; int L = 0, R = N;
inline void upd(int v, int vl, int vr, int x, int y, int d) {
if (!t[v]) t[v] = new node();
upd(t[v], L, R, y, d);
if (vl == vr) return;
int m = vl + vr >> 1;
if (x <= m) upd(2 * v + 1, vl, m, x, y, d);
else upd(2 * v + 2, m + 1, vr, x, y, d);
}
inline int get(int v, int vl, int vr, int l, int r, int l1, int r1) {
if (l > r) return 0;
else if (vl == l && vr == r) return (!t[v] ? 0 : get(t[v], L, R, l1, r1));
int m = vl + vr >> 1;
int a = get(2 * v + 1, vl, m, l, min(r, m), l1, r1);
int b = get(2 * v + 2, m + 1, vr, max(l, m + 1), r, l1, r1);
return a + b;
}
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) {
int n = N;
int m = sz(X); int q = sz(S);
ve<array<int,3>> e(m);
for (int i = 0; i < m; ++i) {
int v, u;
tie(v, u) = mpp(X[i], Y[i]);
e[i] = {min(v, u), v, u};
} sort(all(e));
w1 = w2 = n;
for (int i = 0; i < n; ++i) p1[i] = p2[i] = i;
ve<array<int,5>> que(q);
for (int i = 0; i < q; ++i) que[i] = {S[i], E[i], L[i], R[i], i};
sort(all(que), [](const auto &a, const auto &b) { return a[2] > b[2]; });
ve<int> rt1(q), rt2(q);
int ptr = sz(e) - 1, ptr1 = 0;
for (auto &[v, u, l, r, id] : que) {
while (~ptr && e[ptr][0] >= l) {
add1(e[ptr][1], e[ptr][2]);
--ptr;
} rt1[id] = par1(v);
}
for (int i = 0; i < m; ++i) {
int v, u;
tie(v, u) = mpp(X[i], Y[i]);
e[i] = {max(v, u), v, u};
} sort(all(e));
sort(all(que), [](const auto &a, const auto &b) { return a[3] < b[3]; });
for (auto &[v, u, l, r, id] : que) {
while (ptr1 < sz(e) && e[ptr1][0] <= r) {
add2(e[ptr1][1], e[ptr1][2]);
++ptr1;
} rt2[id] = par2(u);
}
for (int i = 0; i < w1; ++i) if (p1[i] == i) dfs1(i);
for (int i = 0; i < w2; ++i) if (p2[i] == i) dfs2(i);
/*
cout << '\n';
for (int i = 0; i < n; ++i) cout << in1[i] << " " << in2[i] << '\n';
cout << '\n';
for (int i = 0; i < q; ++i) {
cout << "query " << i + 1 << ": " << '\n';
cout << "vertices >= l: [" << in1[rt1[i]] << ", " << out1[rt1[i]] << "]" << '\n';
cout << "vertices <= r: [" << in2[rt2[i]] << ", " << out2[rt2[i]] << "]" << '\n';
cout << '\n';
}
cout << '\n';
*/
int me = ti1;
ve<int> ans(q);
for (int i = 0; i < n; ++i) upd(0, 0, me, in1[i], in2[i], 1);
for (int i = 0; i < q; ++i) ans[i] = get(0, 0, me, in1[rt1[i]], out1[rt1[i]], in2[rt2[i]], out2[rt2[i]]) > 0;
return ans;
}
