#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MID ((l+r)/2)
const ll N=2e5;
vector<ll> g[N];
ll c=0, idx[N], a[N];
void dfs(ll curr, ll prev){
a[c]=curr;
idx[curr]=c;
c++;
}
struct query{
ll s, e, l, r, idx;
ll hl, hr, wl, wr;
};
bool comp_l(query a, query b){
return a.l<b.l;
}
bool comp_r(query a, query b){
return a.r<b.r;
}
bool comp_i(query a, query b){
return a.idx<b.idx;
}
struct DSU{
ll p[N];
ll l[N], r[N];
void init(ll n){
for(ll i=0; i<n; i++){
p[i]=i;
l[i]=i;
r[i]=i;
}
}
ll find(ll u){
if(p[u]==u) return u;
else return p[u]=find(p[u]);
}
void merge(ll u, ll v){
u=find(u);
v=find(v);
l[u]=min(l[u],l[v]);
r[u]=max(r[u],r[v]);
p[v]=u;
}
};
vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> qs, vector<int> qe, vector<int> ql, vector<int> qr) {
for(ll i=0; i<u.size(); i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
for(ll i=0; i<n; i++){
if(g[i].size()==1){
dfs(i,i);
break;
}
}
query q[qs.size()];
for(ll i=0; i<qs.size(); i++){
q[i]={qs[i],qe[i],ql[i],qr[i],i};
}
DSU dsu;
dsu.init(n);
sort(q,q+qs.size(),comp_l);
ll l=n;
for(auto curr:q){
while(curr.l<l){
l--;
if(0<idx[l] && a[idx[l]-1]>=l) dsu.merge(idx[l],idx[l]-1);
if(idx[l]<n-1 && a[idx[l]+1]>=l) dsu.merge(idx[l],idx[l]+1);
}
curr.hl=dsu.l[dsu.find(idx[curr.s])];
curr.hr=dsu.r[dsu.find(idx[curr.s])];
}
dsu.init(n);
sort(q,q+qs.size(),comp_r);
ll r=-1;
for(auto curr:q){
while(r<curr.r){
r++;
if(0<idx[r] && a[idx[r]-1]<=r) dsu.merge(idx[r],idx[r]-1);
if(idx[r]<n-1 && a[idx[r]+1]<=r) dsu.merge(idx[r],idx[r]+1);
}
curr.wl=dsu.l[dsu.find(idx[curr.e])];
curr.wr=dsu.r[dsu.find(idx[curr.e])];
}
sort(q,q+qs.size(),comp_i);
vector<int> ans;
for(auto curr:q){
if(curr.s<curr.e){
if(curr.wl<=curr.hr) ans.push_back(1);
else ans.push_back(0);
}
else{
if(curr.hl<=curr.wr) ans.push_back(1);
else ans.push_back(0);
}
}
return ans;
}
