#include "werewolf.h"
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 1e6+5 , inf = 2e9 + 7 , block = 1000;
const ll INF = 1e18 , mod = 1e9+7;
int p[N][2] , sz[N][2];
int get(int a , int k){
if(p[a][k] == a) return a;
return p[a][k] = get(p[a][k],k);
}
void merge(int a , int b , int k){
a = get(a,k);
b = get(b,k);
if(a == b) return;
if(sz[a][k] < sz[b][k]) swap(a,b);
sz[a][k] += sz[b][k];
p[b][k] = a;
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e , vector<int> l, vector<int> r) {
vector<int> ans;
for(int i = 0; i < s.size(); i++){
for(int j = 0; j < n; j++){
p[j][0] = p[j][1] = j;
sz[j][0] = sz[j][1] = 1;
}
for(int j = 0; j < x.size(); j++){
if(x[j] >= l[i] && y[j] >= l[i]){
merge(x[j],y[j],0);
}
if(x[j] <= r[i] && y[j] <= r[i]){
merge(x[j],y[j],1);
}
}
int ok = 0;
for(int j = 0; j < n; j++){
if(get(s[i] , 0) == get(j , 0) && get(e[i] , 1) == get(j , 1)){
ok = 1;
break;
}
}
ans.push_back(ok);
}
return ans;
}
