#include "werewolf.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 1<<18;
using vi = vector<int>;
int TIME = -1;
struct dsu {
vi r, p;
vector<vi> ch;
vector<array<int, 2>> range;
vector<vector<array<int, 2>>> h;
dsu(int n) : r(n, 1), ch(n), h(n), p(n), range(n) {
iota(all(p), 0);
fill(all(range), array<int, 2>{0, 1});
for(int i = 0; i < n; i++) ch[i].push_back(i), h[i].push_back({n+1, i});
}
int par(int i) {
return i == p[i] ? i : p[i] = par(p[i]);
}
void unite(int i, int j) {
i = par(i), j = par(j);
if(i == j) return;
if(r[i] < r[j]) swap(i, j);
p[j] = i;
range[i][1] += r[j];
for(auto v : ch[j]) {
ch[i].push_back(v);
h[v].push_back({TIME, i});
range[v][0] += r[i];
}
r[i] += r[j];
}
};
vi g[maxn], gt[maxn];
vi cl[maxn], cr[maxn], ev[maxn];
array<int, 2> range[maxn];
set<array<int, 2>> req[maxn];
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
int q = s.size();
vi ans(q), ipar(q), tp(q);
for(int i = 0; i < x.size(); i++) {
if(x[i] < y[i]) swap(x[i], y[i]);
g[x[i]].push_back(y[i]);
gt[y[i]].push_back(x[i]);
}
for(int i = 0; i < q; i++)
cl[l[i]].push_back(i), cr[r[i]].push_back(i);
dsu f(n), b(n);
for(int i = 0; i < n; i++) {
for(auto v : g[i]) f.unite(i, v);
for(auto j : cr[i]) {
tp[j] = f.par(e[j]);
range[j] = f.range[tp[j]];
}
}
for(int j = 0; j < q; j++) {
int t = tp[j];
range[j][1] -= range[j][0];
range[j][0] = f.range[t][0];
range[j][1] += f.range[t][0];
ev[range[j][0]].push_back(j);
ev[range[j][1]].push_back(-j-1);
//cout << e[j] << " " << range[j][0] << " " << range[j][1] << '\n';
}
for(int i = n; i--;) {
TIME = i;
for(auto v : gt[i]) b.unite(i, v);
for(auto j : cl[i]) ipar[j] = b.par(s[j]);//, cout << j << " " << ipar[j] << '\n';
}
vi ord(n);
for(int i = 0; i < n; i++) ord[f.range[i][0]] = i;
int T = 0;
for(auto i : ord) {
for(auto j : ev[T])
if(j >= 0) {
int p = ipar[j];
req[p].insert({l[j], j});
} else {
j = -(j+1);
//cout << "REMOVE " << j << " " << T << endl;
int p = ipar[j];
if(req[p].count({l[j], j})) ans[j] = 1, req[p].erase({l[j], j});
ans[j] ^= 1;
}
//cout << i << " :\n";
for(auto [t, p] : b.h[i]) {
//cout << t << " " << p << "p\n";
while(!req[p].empty() && req[p].begin()->at(0) <= t) {
//cout << " Moment " << T << " " << range[req[p].begin()->at(1)][1] << '\n';
req[p].erase(req[p].begin());
}
}
//cout << '\n';
++T;
}
for(int i = 0; i < q; i++) ans[i] &= s[i] >= l[i] && e[i] <= r[i];
return ans;
}
