#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int N, A[800000], id[400000], f[200000], l[2][2][400000], y, z;
pair<int, int> B[800000];
vector<int> adj[2][400000], rs;
vector<pair<int, int> > v;
vector<tuple<int, int, int, int, int> > qr;
inline int frt(int i) {return i == id[i] ? i : id[i] = frt(id[i]);}
inline void ufds(int t, int a, int b) {
a = frt(a);
b = frt(b);
if (a == b) return;
adj[t][a].push_back(y);
adj[t][b].push_back(y);
adj[t][y].push_back(a);
adj[t][y].push_back(b);
id[a] = id[b] = y++;
}
void it(int t, int i, int o) {
l[t][0][i] = z;
for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i);
if (i < N) {
if (!t) f[z++] = i;
else ++z;
}
l[t][1][i] = z - 1;
}
void init(int i, int a, int b) {
A[i] = INT_MAX;
B[i] = make_pair(a, b);
if (a >= b) return;
init(i * 2, a, (a + b) / 2);
init(i * 2 + 1, (a + b) / 2 + 1, b);
}
int q(int i, int a, int b) {
if (b < B[i].first || B[i].second < a) return INT_MAX;
if (a <= B[i].first && B[i].second <= b) return A[i];
return min(q(i * 2, a, b), q(i * 2 + 1, a, b));
}
void u(int i, int p, int v) {
if (p < B[i].first || B[i].second < p) return;
if (p <= B[i].first && B[i].second <= p) {A[i] = v; return;}
u(i * 2, p, v);
u(i * 2 + 1, p, v);
A[i] = min(A[i * 2], A[i * 2 + 1]);
}
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 = X.size(), Q = S.size(), i, j;
rs.assign(Q, 0);
for (i = 0; i < Q; ++i) qr.emplace_back(R[i], L[i], E[i], S[i], i);
for (i = 0; i < M; ++i) v.emplace_back(max(X[i], Y[i]), min(X[i], Y[i]));
sort(v.begin(), v.end());
sort(qr.begin(), qr.end());
iota(id, id + N * 2 - 1, 0);
y = N;
for (i = j = 0; i < M; ++i) {
while (j < Q && get<0>(qr[j]) < v[i].first) get<2>(qr[j]) = frt(get<2>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j;
ufds(0, v[i].first, v[i].second);
swap(v[i].first, v[i].second);
}
while (j < Q) get<3>(qr[j]) = frt(get<3>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j;
sort(v.begin(), v.end());
sort(qr.begin(), qr.end());
iota(id, id + N * 2 - 1, 0);
y = N;
for (i = M - 1, j = Q - 1; i > -1; --i) {
while (j > -1 && get<0>(qr[j]) > v[i].first) get<3>(qr[j]) = frt(get<3>(qr[j])), --j;
ufds(1, v[i].first, v[i].second);
}
while (j > -1) get<2>(qr[j]) = frt(get<2>(qr[j])), --j;
it(0, N * 2 - 2, -1);
z = 0;
it(1, N * 2 - 2, -1);
for (i = 0; i < Q; ++i) get<0>(qr[i]) = l[0][0][get<2>(qr[i])], get<1>(qr[i]) = l[0][1][get<2>(qr[i])];
sort(qr.begin(), qr.end());
init(1, 0, N - 1);
for (i = Q - 1, j = N - 1; i > -1; --i) {
while (j >= get<0>(qr[i])) u(1, l[1][0][f[j]], j), --j;
rs[get<4>(qr[i])] = q(1, l[1][0][get<3>(qr[i])], l[1][1][get<3>(qr[i])]) <= get<1>(qr[i]);
}
return rs;
}
