#include <bits/stdc++.h>
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r)-1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)(x).size()
#define ALL(x) begin(x), end(x)
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
#include "werewolf.h"
class UF {
V<i32> par;
V<pair<i32, i32>> mnx;
public:
UF(i32 n) : par(n, -1), mnx(n) {
REP(i, n) {
mnx[i] = pair<i32, i32>(i, i);
}
}
i32 root(i32 x) {
if (par[x] < 0) {
return x;
} else {
return par[x] = root(par[x]);
}
}
pair<i32, i32> get_minmax(i32 v) {
i32 r = root(v);
return mnx[r];
}
bool unite(i32 x, i32 y) {
x = root(x);
y = root(y);
if (x == y) {
return false;
}
if (-par[x] > -par[y]) {
swap(x, y);
}
chmin(mnx[y].first, mnx[x].first);
chmax(mnx[y].second, mnx[x].second);
par[y] += par[x];
par[x] = y;
return true;
}
};
V<i32> check_validity(i32 n, V<i32> x, V<i32> y, V<i32> s, V<i32> e, V<i32> l, V<i32> r) {
i32 q = LEN(s);
V<V<i32>> g(n);
REP(i, LEN(x)) {
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
V<i32> par0(n, -1), par1(n, -1);
{
V<V<i32>> process(n);
REP(i, q) {
process[l[i]].push_back(i);
}
UF uf(n);
PER(i, n) {
for (i32 j : g[i]) {
if (j > i) {
i32 tmp = uf.get_minmax(j).first;
if (uf.unite(i, j)) {
par0[tmp] = i;
}
}
}
for (i32 j : process[i]) {
s[j] = uf.get_minmax(s[j]).first;
}
}
}
{
V<V<i32>> process(n);
REP(i, q) {
process[r[i]].push_back(i);
}
UF uf(n);
REP(i, n) {
for (i32 j : g[i]) {
if (j < i) {
i32 tmp = uf.get_minmax(j).second;
if (uf.unite(i, j)) {
par1[tmp] = i;
}
}
}
for (i32 j : process[i]) {
e[j] = uf.get_minmax(e[j]).second;
}
}
}
V<i32> ans(q, 0);
constexpr i32 B = 64;
using u64 = unsigned long long;
i32 blk = (q + B + 1) / B;
V<u64> dp0(n, 0), dp1(n, 0);
REP(iter, blk) {
i32 l = B * iter;
i32 r = min(q, l + B);
REP(i, n) {
dp0[i] = dp1[i] = 0;
}
REP(i, l, r) {
dp0[s[i]] ^= 1ull << (i - l);
dp1[e[i]] ^= 1ull << (i - l);
}
REP(i, 1, n) {
dp0[i] |= dp0[par0[i]];
}
PER(i, n - 1) {
dp1[i] |= dp1[par1[i]];
}
u64 t = 0;
REP(i, n) {
t |= dp0[i] & dp1[i];
}
REP(i, l, r) {
if (t & (1ull << (i - l))) {
ans[i] = 1;
}
}
}
return ans;
}
