#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"
const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const ll MOD = 998244353;
const int maxl = 20;
const ll P = 31;
int n;
vector<tuple<int, int, int>> g[maxn];
struct asd{
int t;
int nxt[maxl][maxn];
vector<int> g[maxn];
int p[maxn], a[maxn];
int tin[maxn], tout[maxn];
void calc(){
for(int i = 1; i <= n; i++){
p[i] = i;
}
} int get(int v){
if(p[v] == v) return v;
return p[v] = get(p[v]);
} void join(int a, int b, int c){
a = get(a), b = get(b);
if(a == b) return;
if((a < b) != c) swap(a, b);
// cout << a << ' ' << b << ' ' << c << ent;
p[b] = a; g[a].push_back(b);
} void dfs(int v){
tin[v] = ++t;
a[t] = v;
for(int k = 1; k < maxl; k++){
nxt[k][v] = nxt[k-1][nxt[k-1][v]];
}
for(int to: g[v]){
nxt[0][to] = v;
dfs(to);
} tout[v] = t;
}
} A, B;
int d[maxn * 4];
void upd(int i, int x, int v = 1, int tl = 1, int tr = n){
d[v] = max(d[v], x);
if(tl < tr){
int mid = (tl + tr) >> 1;
if(i <= mid) upd(i, x, v<<1, tl, mid);
else upd(i, x, v<<1|1, mid+1, tr);
}
} int get(int l, int r, int v = 1, int tl = 1, int tr = n){
if(tl > r || tr < l) return 0;
if(l <= tl && tr <= r) return d[v];
int mid = (tl + tr) >> 1;
return max(get(l, r, v<<1, tl, mid)
, get(l, r, v<<1|1, mid+1, tr));
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
n = N;
vector<pii> e;
for(int i = 0; i < X.size(); i++){
e.push_back({X[i] + 1, Y[i] + 1});
} sort(e.begin(), e.end(), [](pii a, pii b){
return max(a.first, a.second) <
max(b.first, b.second);
}); B.calc(); A.calc();
for(auto [a, b]: e) B.join(a, b, 0);
sort(e.begin(), e.end(), [](pii a, pii b){
return min(a.first, a.second) >
min(b.first, b.second);
}); for(auto [a, b]: e) A.join(a, b, 1);
A.dfs(1); B.dfs(n);
vector<int> ans(S.size(), 0);
for(int i = 0; i < S.size(); i++){
int a = S[i] + 1, b = E[i] + 1;
L[i]++; R[i]++;
for(int k = maxl - 1; k >= 0; k--){
if(A.nxt[k][a] && A.nxt[k][a] >= L[i]){
a = A.nxt[k][a];
} if(B.nxt[k][b] && B.nxt[k][b] <= R[i]){
b = B.nxt[k][b];
}
}
// cout << a << ' ' << A.tin[a] << ' ' << A.tout[a] << ": ";
// for(int i = A.tin[a]; i <= A.tout[a]; i++){
// cout << A.a[i] << ' ';
// } cout << ent;
// cout << b << ' ' << B.tin[b] << ' ' << B.tout[b] << ": ";
// for(int i = B.tin[b]; i <= B.tout[b]; i++){
// cout << B.a[i] << ' ';
// } cout << ent;
g[A.tout[a]].push_back({a, b, i});
} for(int i = 1; i <= n; i++){
upd(B.tin[A.a[i]], i);
for(auto [a, b, id]: g[i]){
if(get(B.tin[b], B.tout[b]) >= A.tin[a]){
ans[id] = 1;
}
}
} return ans;
}
