#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 2e5+50;
int dsu[nax];
int sz_sg[nax],p_sg[nax][20],fr_sg[nax],to_sg[nax],val_sg[nax],nxt_sg[nax],seg_sg[nax],d_sg[nax];
int sz_bg[nax],p_bg[nax][20],fr_bg[nax],to_bg[nax],val_bg[nax],nxt_bg[nax],seg_bg[nax],d_bg[nax];
int n,m,T = 1;
vector<int> sg[nax],bg[nax];
// DSU
int find(int u){
return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}
// HLD SMALL Graph
void dfs_sz_sg(int u,int p){
sz_sg[u] = 1;
for(auto &v: sg[u]) {
if(v == p)continue;
d_sg[v] = d_sg[u] + 1;
p_sg[v][0] = u;
for(int i=1;i<20;i++)p_sg[v][i] = p_sg[p_sg[v][i-1]][i-1];
dfs_sz_sg(v,u);
sz_sg[u] += sz_sg[v];
if(sz_sg[v] > sz_sg[sg[u][0]]) {
swap(v, sg[u][0]);
}
}
}
void dfs_hld_sg(int u,int par) {
fr_sg[u] = T++;
val_sg[fr_sg[u]] = u;
for(auto v: sg[u]) {
if(v == par)continue;
nxt_sg[v] = (v == sg[u][0] ? nxt_sg[u] : v);
dfs_hld_sg(v,u);
}
to_sg[u] = T;
}
void hld_sg(){
T=1;
dfs_sz_sg(1,0);
dfs_hld_sg(1,0);
}
// HLD BIG Graph
void dfs_sz_bg(int u,int p){
sz_bg[u] = 1;
for(auto &v: bg[u]) {
if(v == p)continue;
d_bg[v] = d_bg[u] + 1;
p_bg[v][0] = u;
for(int i=1;i<20;i++)p_bg[v][i] = p_bg[p_bg[v][i-1]][i-1];
dfs_sz_bg(v,u);
sz_bg[u] += sz_bg[v];
if(sz_bg[v] > sz_bg[bg[u][0]]) {
swap(v, bg[u][0]);
}
}
}
void dfs_hld_bg(int u,int par) {
fr_bg[u] = T++;
val_bg[fr_bg[u]] = u;
for(auto v: bg[u]) {
if(v == par)continue;
nxt_bg[v] = (v == bg[u][0] ? nxt_bg[u] : v);
dfs_hld_bg(v,u);
}
to_bg[u] = T;
}
void hld_bg(){
T=1;
dfs_sz_bg(n,0);
dfs_hld_bg(n,0);
}
// SMALL Tree Segment tree
void build_sg(int n,int s,int e){
if(s == e){
seg_sg[n] = val_sg[s];
return;
}
build_sg(n*2,s,(s+e)/2);
build_sg(n*2+1,(s+e)/2+1,e);
seg_sg[n] = max( seg_sg[n*2] , seg_sg[n*2+1] );
}
int get_sg(int n,int s,int e,int l,int r){
if(s > r || e < l)return 0;
if(s >= l && e <= r)return seg_sg[n];
return max( get_sg(n*2,s,(s+e)/2,l,r) , get_sg(n*2+1,(s+e)/2+1,e,l,r) );
}
// BIG Tree Segment tree
void build_bg(int n,int s,int e){
if(s == e){
seg_bg[n] = val_bg[s];
return;
}
build_bg(n*2,s,(s+e)/2);
build_bg(n*2+1,(s+e)/2+1,e);
seg_bg[n] = min( seg_bg[n*2] , seg_bg[n*2+1] );
}
int get_bg(int n,int s,int e,int l,int r){
if(s > r || e < l)return 1e9;
if(s >= l && e <= r)return seg_bg[n];
return min( get_bg(n*2,s,(s+e)/2,l,r) , get_bg(n*2+1,(s+e)/2+1,e,l,r) );
}
// SMALL TREE LCA
int kth_sg(int u,int dif){
for(int k = 19;k>=0;k--){
if( (dif >> k) & 1 ){
u = p_sg[u][k];
}
}
return u;
}
int lca_sg(int u,int v){
if(d_sg[u] < d_sg[v])swap(u,v);
int dif = d_sg[u] - d_sg[v];
assert(dif >= 0);
u = kth_sg(u,dif);
if(u == v)return u;
for(int k=19;k>=0;k--){
if(p_sg[u][k] != p_sg[v][k]){
u = p_sg[u][k];
v = p_sg[v][k];
}
}
assert(u!=v);
return p_sg[u][0];
}
// BIG Tree LCA
int kth_bg(int u,int dif){
for(int k = 19;k>=0;k--){
if( (dif >> k) & 1 ){
u = p_bg[u][k];
}
}
return u;
}
int lca_bg(int u,int v){
if(d_bg[u] < d_bg[v])swap(u,v);
int dif = d_bg[u] - d_bg[v];
assert(dif >= 0);
u = kth_bg(u,dif);
if(u == v)return u;
for(int k=19;k>=0;k--){
if(p_bg[u][k] != p_bg[v][k]){
u = p_bg[u][k];
v = p_bg[v][k];
}
}
assert(u!=v);
return p_bg[u][0];
}
// Answring Queries
int find_smallest(int u,int v,int l,int r){
int small = -1;
int w = lca_bg(u,v);
assert(w);
bool done = 0;
int tmp,lo,hi,md;
for(int x = u;!done;x=p_bg[nxt_bg[x]][0]){
if(d_bg[nxt_bg[x]] <= d_bg[w]){
tmp = get_bg(1,1,n,fr_bg[w],fr_bg[x]);
lo = fr_bg[w];hi = fr_bg[x];
done = 1;
}else{
tmp = get_bg(1,1,n,fr_bg[nxt_bg[x]],fr_bg[x]);
lo = fr_bg[nxt_bg[x]];hi = fr_bg[x];
}
if(tmp < l){
int lim = hi;
small = lo;
while(lo <= hi){
md = (lo + hi)/2;
int cur = get_bg(1,1,n,md,lim);
if(cur >= l){
small = md;
hi = md-1;
}else lo = md+1;
}
assert(small);
return small;
}
}
done = 0;
vector<pair<int,pair<int,int>>> ranges;
for(int x = v;!done;x=p_bg[nxt_bg[x]][0]){
if(d_bg[nxt_bg[x]] <= d_bg[w]){
tmp = get_bg(1,1,n,fr_bg[w],fr_bg[x]);
lo = fr_bg[w];hi = fr_bg[x];
done = 1;
}else{
tmp = get_bg(1,1,n,fr_bg[nxt_bg[x]],fr_bg[x]);
lo = fr_bg[nxt_bg[x]];hi = fr_bg[x];
}
ranges.push_back({tmp,{lo,hi}});
}
reverse(ranges.begin(),ranges.end());
for(auto cur : ranges){
lo = cur.second.first;
hi = cur.second.second;
int lim = lo;
int val = cur.first;
if(val < l){
small = lo;
while(lo <= hi){
md = (lo + hi)/2;
int cur = get_bg(1,1,n,lim,md);
if(cur >= l){
small = md;
lo = md+1;
}else hi = md-1;
}
assert(small);
return small;
}
}
return 0;
}
int find_largest(int u,int v,int l,int r){
int w = lca_sg(u,v);
int tmp;
assert(w);
bool done = 0;
for(int x = u;!done;x=p_sg[nxt_sg[x]][0]){
if(d_sg[nxt_sg[x]] <= d_sg[w]){
tmp = get_sg(1,1,n,fr_sg[w],fr_sg[x]);
done = 1;
}else{
tmp = get_sg(1,1,n,fr_sg[nxt_sg[x]],fr_sg[x]);
}
if(tmp > r)return 0;
}
done = 0;
for(int x = v;!done;x=p_sg[nxt_sg[x]][0]){
if(d_sg[nxt_sg[x]] <= d_sg[w]){
tmp = get_sg(1,1,n,fr_sg[w],fr_sg[x]);
done = 1;
}else{
tmp = get_sg(1,1,n,fr_sg[nxt_sg[x]],fr_sg[x]);
}
if(tmp > r)return 0;
}
return 1;
}
int solve(int fr,int to,int l,int r){
fr = find_smallest(fr,to,l,r);
if(fr == 0)return 1;
fr = get_bg(1,1,n,fr,fr);
if(fr > r || fr < l)return 0;
return find_largest(fr,to,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) {
n = N;
m = x.size();
int Q = S.size();
vector<vector<int>> tmp(n+1);
for(int i=0;i<m;i++){
int u = x[i];
int v = y[i];
u++;v++;
tmp[u].push_back(v);
tmp[v].push_back(u);
}
for(int i=1;i<=n;i++){
sort(tmp[i].begin(),tmp[i].end());
dsu[i] = i;
}
for(int u=1;u<=n;u++){
for(int v : tmp[u]){
if(find(v) == find(u) || u > v)continue;
sg[u].push_back(v);
sg[v].push_back(u);
dsu[find(v)] = find(u);
}
}
for(int i=1;i<=n;i++){
reverse(tmp[i].begin(),tmp[i].end());
dsu[i] = i;
}
for(int u=n;u>=1;u--){
for(int v : tmp[u]){
if(find(v) == find(u) || u < v)continue;
bg[u].push_back(v);
bg[v].push_back(u);
dsu[find(v)] = find(u);
}
}
for(int i=1;i<=n;i++){
nxt_sg[i] = 1;
nxt_bg[i] = n;
}
hld_sg();
hld_bg();
build_sg(1,1,n);
build_bg(1,1,n);
vector<int> A(Q,0);
for (int i = 0; i < Q; ++i) {
S[i]++;E[i]++;L[i]++;R[i]++;
A[i] = solve(S[i],E[i],L[i],R[i]);
}
return A;
}
