#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e9+10;
const int maxn = 4e5+10;
const int lg = 18;
int n, tin[2][maxn], tout[2][maxn], timer, tr[4*maxn];
int ds[2][maxn], dsz[2][maxn];
pair<int,int> p[2][lg+1][maxn];
vector<pair<int,int>> g[2][maxn];
int find(int id, int v) {
if(ds[id][v] == v) return v;
return ds[id][v] = find(id,ds[id][v]);
}
void join(int id, int u, int v, int w) {
u = find(id,u);
v = find(id,v);
if(u == v) return;
if(dsz[id][u] < dsz[id][v]) swap(u,v);
//cout << id << " " << u << " " << v << " " << w << endl;
ds[id][v] = u;
dsz[id][u]+= dsz[id][v];
g[id][u].pb(mp(w,v));
p[id][0][v] = mp(u,w);
}
void dfseulertour(int id, int u, int ant) {
tin[id][u] = ++timer;
for(auto V : g[id][u]) if(V.sc != ant) {
int v = V.sc;
int w = V.fr;
dfseulertour(id,v,u);
}
tout[id][u] = timer;
}
void upd(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
tr[no] = val;
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
upd(lc,l,mid,pos,val);
upd(rc,mid+1,r,pos,val);
tr[no] = min(tr[lc],tr[rc]);
}
int query(int no, int l, int r, int L, int R) {
if(l > R || r < L) return inf;
if(l >= L && r <= R) return tr[no];
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
return min(query(lc,l,mid,L,R),query(rc,mid+1,r,L,R));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
// int Q = S.size();
// std::vector<int> A(Q);
// for (int i = 0; i < Q; ++i) {
// A[i] = 0;
// }
// return A;
n = N;
for(int i = 0; i < n; i++) {
ds[0][i] = ds[1][i] = i;
dsz[0][i] = dsz[1][i] = 1;
p[0][0][i] = p[1][0][i] = mp(i,i);
}
vector<pair<int,pair<int,int>>> edgs0;
for(int i = 0; i < (int) X.size(); i++) {
int u = X[i];
int v = Y[i];
edgs0.pb(mp(min(u,v),mp(u,v)));
}
sort(all(edgs0),greater<pair<int,pair<int,int>>>());
for(auto X : edgs0) {
int w = X.fr;
int u = X.sc.fr;
int v = X.sc.sc;
join(0,u,v,w);
}
vector<pair<int,pair<int,int>>> edgs1;
for(int i = 0; i < (int) X.size(); i++) {
int u = X[i];
int v = Y[i];
edgs1.pb(mp(max(u,v),mp(u,v)));
}
sort(all(edgs1));
for(auto X : edgs1) {
int w = X.fr;
int u = X.sc.fr;
int v = X.sc.sc;
join(1,u,v,w);
}
for(int id = 0; id <= 1; id++) {
for(int b = 1; b <= lg; b++) {
for(int i = 0; i < n; i++) {
p[id][b][i].fr = p[id][b-1][p[id][b-1][i].fr].fr;
if(id == 0) p[id][b][i].sc = min(p[id][b-1][p[id][b-1][i].fr].sc,p[id][b-1][i].sc);
else p[id][b][i].sc = max(p[id][b-1][p[id][b-1][i].fr].sc,p[id][b-1][i].sc);
}
}
}
timer = 0; dfseulertour(0,find(0,0),-1);
timer = 0; dfseulertour(1,find(1,0),-1);
vector<pair<pair<pair<int,int>,pair<int,int>>,int>> qrys;
for(int i = 0; i < S.size(); i++) {
int lbs = 0;
int rbs = 0;
int s = S[i];
for(int b = lg; b >= 0; b--) {
// cout << s << " " << p[0][s][b].sc << endl;
if(p[0][b][s].sc >= L[i]) {
s = p[0][b][s].fr;
}
}
int ls = tin[0][s];
int rs = tin[0][s];
lbs = 0;
rbs = (int) g[0][s].size()-1;
while(lbs <= rbs) {
int mid = (lbs+rbs)/2;
if(g[0][s][mid].fr >= L[i]) {
rs = tout[0][g[0][s][mid].sc];
lbs = mid+1;
}
else {
rbs = mid-1;
}
}
// cout << s << " " << ls << " " << rs << endl;
int e = E[i];
for(int b = lg; b >= 0; b--) {
if(p[1][b][e].sc <= R[i]) {
e = p[1][b][e].fr;
}
}
int le = tin[1][e];
int re = tin[1][e];
lbs = 0;
rbs = (int) g[1][e].size()-1;
while(lbs <= rbs) {
int mid = (lbs+rbs)/2;
if(g[1][e][mid].fr <= R[i]) {
re = tout[1][g[1][e][mid].sc];
lbs = mid+1;
}
else {
rbs = mid-1;
}
}
// cout << le << " " << re << endl;
qrys.pb(mp(mp(mp(le,re),mp(ls,rs)),i));
}
for(int i = 0; i < n; i++) {
qrys.pb(mp(mp(mp(tin[1][i],inf),mp(i,-1)),0));
upd(1,1,n,tin[0][i],tin[1][i]);
//cout << " " << tin[0][i] << " " << tin[1][i] << endl;
}
sort(all(qrys));
vector<int32_t> ans((int) S.size());
for(auto X : qrys) {
if(X.fr.sc.sc == -1) {
int v = X.fr.sc.fr;
upd(1,1,n,tin[0][v],inf);
}
else {
int ls = X.fr.sc.fr;
int rs = X.fr.sc.sc;
int re = X.fr.fr.sc;
int idqry = X.sc;
//cout << query(1,1,n,ls,rs) << endl;
if(query(1,1,n,ls,rs) <= re) {
ans[idqry] = 1;
}
else {
ans[idqry] = 0;
}
}
}
return ans;
}
