#include "werewolf.h"
#include <bits/stdc++.h>
#define ar array
#define all(v) v.begin(),v.end()
using namespace std;
const int N = 1e6;
const int LOG = 20;
namespace HM{
int T;
int p[N];
vector<int> g[N];
int fnd(int x){
if(p[x] == x)return x;
return p[x] = fnd(p[x]);
}
int A[N];
void upd(int a,int b,int w){
a = fnd(a);
b = fnd(b);
p[a] = p[b] = T;
A[T] = w;
g[T].push_back(a);
if(a != b)g[T].push_back(b);
T++;
}
vector<int> ord;
int L[N], R[N];
int up[N][LOG];
void dfs(int x,int p){
up[x][0] = p;
for(int i = 1;i < LOG;i++)up[x][i] = up[up[x][i - 1]][i - 1];
if(g[x].empty()){
ord.push_back(x);
L[x] = R[x] = ord.size() - 1;
return;
}
L[x] = ord.size();
for(auto u: g[x])dfs(u, x);
R[x] = ord.size() - 1;
}
void bld(int n, vector<int> x, vector<int> y){
vector<ar<int,2> > e;
int m = x.size();
for(int i = 0;i < m;i++)e.push_back({x[i], y[i]});
sort(all(e), [&](ar<int,2> a, ar<int,2> b) -> bool{
return min(a[0], a[1]) > min(b[0], b[1]);
});
T = n;
for(int i = 0;i < n + m;i++)p[i] = i;
for(auto [a, b]: e)upd(a, b, min(a, b));
dfs(T - 1, T - 1);
}
ar<int,2> qry(int x,int w){
for(int i = LOG - 1;i >= 0;i--){
if(A[up[x][i]] >= w)x = up[x][i];
}
return {L[x], R[x]};
}
};
namespace WF{
int T;
int p[N];
vector<int> g[N];
int fnd(int x){
if(p[x] == x)return x;
return p[x] = fnd(p[x]);
}
int A[N];
void upd(int a,int b,int w){
a = fnd(a);
b = fnd(b);
p[a] = p[b] = T;
A[T] = w;
g[T].push_back(a);
if(a != b)g[T].push_back(b);
T++;
}
vector<int> ord;
int L[N], R[N];
int up[N][LOG];
void dfs(int x,int p){
up[x][0] = p;
for(int i = 1;i < LOG;i++)up[x][i] = up[up[x][i - 1]][i - 1];
if(g[x].empty()){
ord.push_back(x);
L[x] = R[x] = ord.size() - 1;
return;
}
L[x] = ord.size();
for(auto u: g[x])dfs(u, x);
R[x] = ord.size() - 1;
}
void bld(int n, vector<int> x, vector<int> y){
vector<ar<int,2> > e;
int m = x.size();
for(int i = 0;i < m;i++)e.push_back({x[i], y[i]});
sort(all(e), [&](ar<int,2> a, ar<int,2> b) -> bool{
return max(a[0], a[1]) < max(b[0], b[1]);
});
T = n;
for(int i = 0;i < n + m;i++)p[i] = i;
for(auto [a, b]: e)upd(a, b, max(a, b));
dfs(T - 1, T - 1);
}
ar<int,2> qry(int x,int w){
for(int i = LOG - 1;i >= 0;i--){
if(A[up[x][i]] <= w)x = up[x][i];
}
return {L[x], R[x]};
}
};
struct SGT{
vector<vector<int> > s;
SGT(int n){
s.resize(4 * n);
}
void bld(int k,int tl,int tr,int A[]){
if(tl == tr){
s[k] = {A[tl]};
return;
}
int tm = (tl + tr) / 2;
bld(k * 2, tl, tm, A);
bld(k * 2 + 1, tm + 1, tr, A);
merge(all(s[k * 2]), all(s[k * 2 + 1]), back_inserter(s[k]));
}
int qry(int k,int tl,int tr,int l,int r,int x,int y){
if(l > tr || tl > r)return 0;
if(l <= tl && tr <= r)return upper_bound(all(s[k]), y) - lower_bound(all(s[k]), x);
int tm = (tl + tr) / 2;
return qry(k * 2, tl, tm, l, r, x, y) + qry(k * 2 + 1, tm + 1, tr, l, r, x, y);
}
};
vector<int> check_validity(int n, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
HM::bld(n, X, Y);
WF::bld(n, X, Y);
int A[n];
for(int i = 0;i < n;i++)A[i] = WF::L[HM::ord[i]];
// for(int i = 0;i < n;i++)cout<<A[i]<<" ";
// cout<<'\n';
SGT sgt(n);
sgt.bld(1, 0, n - 1, A);
vector<int> ans;
for(int i = 0;i < S.size();i++){
auto [s, e, l, r] = ar<int,4>{S[i], E[i], L[i], R[i]};
ar<int,2> r1 = HM::qry(s, l);
ar<int,2> r2 = WF::qry(e, r);
if(sgt.qry(1, 0, n - 1, r1[0], r1[1], r2[0], r2[1]))ans.push_back(1);
else ans.push_back(0);
}
return ans;
}
