#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
class DSU {
vi size, par;
int sz;
public:
DSU(int n) {
sz = n;
size = vi(sz, 1);
par = vi(sz);
for (int i = 0; i < sz; i++) par[i] = i;
}
int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); }
bool connected(int x, int y) { return find(x) == find(y); }
bool join(int x, int y) {
if (connected(x, y)) return false;
int px = find(x), py = find(y);
if (size[px] < size[py]) swap(px, py);
size[px] += size[py];
par[py] = px;
return true;
}
};
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int Q = L.size();
int M = X.size();
vi ans(N);
for (int t = 0; t < Q; t++) {
DSU dsuW(N), dsuH(N);
int l = L[t], r = R[t];
for (int i = 0; i < M; i++) {
if (X[i] >= l && Y[i] >= l) dsuH.join(X[i], Y[i]);
if (X[i] <= r && Y[i] <= r) dsuW.join(X[i], Y[i]);
}
for (int i = 0; i < M; i++) {
if (i >= l && i <= r) {
if (dsuH.find(S[t]) == dsuH.find(i) && dsuW.find(E[t]) == dsuW.find(i)) {
ans[t] = 1;
break;
}
}
}
}
return ans;
}
