// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;
#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll
#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
#include "werewolf.h"
struct query {
int id, s, t, l, r;
};
struct event {
int id, ty, t, l, r;
bool operator<(const event& o) const {
return make_pair(t, ty) < make_pair(o.t, o.ty);
}
};
struct fenwick {
int n;vector<int> t;
fenwick(int n):n(n),t(n,0){};
void add(int i, int x) {
for(;i<n;i|=i+1)t[i]+=x;
}
int query(int i) {
int x=0;for(;~i;i=(i&(i+1))-1)x+=t[i];
return x;
}
};
int n,q;
vector<vector<int>> adj;
vector<int> ans;
vector<query> qs;
fenwick ft(0);
struct kruskal_tree {
int m,rt;
vector<int> up;
vector<vector<int>> ch;
vector<int> tin, tout;
vector<vector<int>> bl;
int ti=0;
kruskal_tree() : m(2*n), up(m,-1), ch(m), tin(m), tout(m), bl(20, vector<int>(m)) {}
int find(int x) { return up[x]<0?x:up[x]=find(up[x]); }
void dfs(int v) {
tin[v]=ti;
if(v>=n)ti++;
for(auto x:ch[v])dfs(x);
tout[v]=ti-1;
}
void build(bool rev) {
if(!rev) {
for(int i=0;i<n;i++) {
bl[0][i+n] = up[i+n] = i;
ch[i].push_back(i+n);
for(auto j:adj[i]) {
//for(int i=0;i<m;i++)printf("%d ",up[i]);printf("\n");
int u = find(i+n);
int v = find(j+n);
if(j<i && v!=u) {
//printf("U %d <- %d\n", i, j);
//printf("par %d = %d\n", v, i);
ch[i].push_back(v);
bl[0][v]=up[v]=i;
}
}
}
rt=bl[0][n-1]=n-1;
}
else {
for(int i=n-1;~i;i--) {
bl[0][i+n] = up[i+n] = i;
ch[i].push_back(i+n);
for(auto j:adj[i]) {
int u = find(i+n);
int v = find(j+n);
if(j>i && v!=u) {
//printf("U %d <- %d\n", i, j);
//printf("par %d = %d\n", v, i);
ch[i].push_back(v);
bl[0][v]=up[v]=i;
}
}
}
rt=bl[0][0]=0;
}
for(int l=1;l<20;l++)
for(int i=0;i<m;i++)
bl[l][i]=bl[l-1][bl[l-1][i]];
dfs(rt);
//for(int i=0;i<m;i++)printf("%d ",bl[0][i]);
//printf("\n");
}
int jump(int v, int x) {
bool rev = rt==0;
//printf("jump %d %d (%d) = ",v,x,rev);
if(!rev) {
for(int l=19;~l;l--)
if(bl[l][v]<=x)v=bl[l][v];
}
else {
for(int l=19;~l;l--)
if(bl[l][v]>=x)v=bl[l][v];
}
//printf("%d\n",v);
return v;
}
};
void solve() {
kruskal_tree hkt, wkt;
wkt.build(0);
hkt.build(1);
vector<event> evs;
for(int i=0;i<n;i++) {
evs.push_back({-1, 2, wkt.tin[i+n], hkt.tin[i+n], -1});
//printf("%d %d\n", wkt.tin[i+n], hkt.tin[i+n]);
}
for(auto [id, s,t,l,r] : qs) {
int vw = wkt.jump(t+n, r);
int vh = hkt.jump(s+n, l);
evs.push_back({id, 1, wkt.tin[vw], hkt.tin[vh], hkt.tout[vh]});
evs.push_back({id, 3, wkt.tout[vw], hkt.tin[vh], hkt.tout[vh]});
//printf("%d %d | %d %d\n", wkt.tin[vw], wkt.tout[vw], hkt.tin[vh], hkt.tout[vh]);
}
sort(all(evs));
for(auto [id, ty, t, l, r] : evs) {
//printf("event %d \t%d %d \t| %d %d\n", id, ty, t, l, r);
if(ty==2) ft.add(l, 1);
if(ty==3) ans[id] += ft.query(r)-ft.query(l-1);
if(ty==1) ans[id] -= ft.query(r)-ft.query(l-1);
}
for(auto&x:ans)x=!!x;
}
vector<int> check_validity(int N, vector<int> e1, vector<int> e2,
vector<int> st, vector<int> en,
vector<int> ls, vector<int> rs) {
n=N;
ft=fenwick(n);
adj.resize(n);
q=st.size();
for(int i=0;i<e1.size();i++)
adj[e1[i]].push_back(e2[i]),
adj[e2[i]].push_back(e1[i]);
ans.resize(q);qs.resize(q);
for(int i=0;i<q;i++) qs[i]={i,st[i],en[i],ls[i],rs[i]};
solve();
return ans;
}
