#include "werewolf.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 6e5+10;
const int MAXA = 5e4+10;
const int SQRT = 300;
const int INF = 2e9;
const int MOD = 1e9+87;
const int MOD2 = 1e9+7;
const int LOG = 30;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int n, q, sta[MAXN], en[MAXN], ans[MAXN], l[MAXN], r[MAXN];
array<int,4> que[MAXN];
vector<int> adj[MAXN];
struct dsu {
int par[MAXN];
void bd(){
for(int i=1; i<=MAXN-10; i++) par[i] = i;
}
int f(int x){
return (par[x]==x ? x : par[x] = f(par[x]));
}
bool con(int x, int y){
return f(x) == f(y);
}
void mer(int x, int y){
x = f(x); y = f(y);
par[x] = y;
}
} DSU;
vector<array<int,3>> sol[MAXN];
vector<int> poi[MAXN];
struct seg {
int st[4*MAXN];
int que(int id,int l,int r,int x,int y){
if(x<=l && r<=y) return st[id];
if(r<x || y<l) return 0;
return que(lf,l,md,x,y)+que(rg,md+1,r,x,y);
}
int upd(int id,int l,int r,int x,int y){
if(l==r && l==x) return st[id] += y;
if(r<x || x<l) return st[id];
return st[id] = upd(lf,l,md,x,y)+upd(rg,md+1,r,x,y);
}
} A;
void solve(){
for(int i=1; i<=q; i++){
// for(int j=0; j<4; j++) cout << que[i][j] << ' ';
// cout << " xx\n";
sol[que[i][0]-1].pb({que[i][2], que[i][3], -i});
sol[que[i][1]].pb({que[i][2], que[i][3], i});
}
for(int i=1; i<=n; i++){
for(auto y : poi[i]) A.upd(1,1,n,y,1);
for(auto [l,r,id] : sol[i]){
if(id < 0) ans[-id] -= A.que(1,1,n,l,r);
else ans[id] += A.que(1,1,n,l,r);
}
}
}
vector<int> tree[MAXN];
int vis = 0, val[MAXN], le[MAXN], ri[MAXN];
void dfs(int nw){
if(tree[nw].size() == 0){ // leaf
if(val[nw] != 0){
poi[val[nw]].pb(vis+1);
// cout << nw << ' '<< val[nw] << ' '<< vis+1 << " point\n";
}
val[nw] = ++vis;
}
for(auto nx : tree[nw]) dfs(nx);
}
vector<int> vec[MAXN];
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
n = N; q = S.size();
for(int i=0; i<X.size(); i++){
adj[X[i]+1].pb(Y[i]+1);
adj[Y[i]+1].pb(X[i]+1);
}
for(int i=1; i<=q; i++){
sta[i] = S[i-1]+1, en[i] = E[i-1]+1;
l[i] = L[i-1]+1, r[i] = R[i-1]+1;
vec[r[i]].pb(i);
// l[i] <= human, were <= r[i]
}
{//were
DSU.bd();
int cnt = n;
for(int i=1; i<=n; i++){
for(auto nx : adj[i]){
if(nx > i) continue;
if(DSU.con(nx, i)) continue;
++cnt;
int a = DSU.f(nx), b = DSU.f(i);
DSU.mer(a, cnt); DSU.mer(b, cnt);
tree[cnt].pb(a); tree[cnt].pb(b);
}
}
dfs(cnt);
DSU.bd();
cnt = n;
for(int i=1; i<=n; i++) le[i] = ri[i] = val[i];
for(int i=1; i<=n; i++){
for(auto nx : adj[i]){
if(nx > i) continue;
if(DSU.con(nx, i)) continue;
++cnt;
int a = DSU.f(nx), b = DSU.f(i);
DSU.mer(a, cnt); DSU.mer(b, cnt);
le[cnt] = min(le[a], le[b]); ri[cnt] = max(ri[a], ri[b]);
// cout << cnt << ' '<< le[cnt] << ' '<< ri[cnt] << "ab\n";
}
for(auto idx : vec[i]){
int s = DSU.f(en[idx]);
que[idx][0] = le[s]; que[idx][1] = ri[s];
// cout << idx <<' '<<en[idx] <<' '<<s<< ' '<< le[s] <<' '<<ri[s] <<" ri\n";
}
}
}
{//human
for(int i=1; i<=MAXN-10; i++){
tree[i].clear(); vec[i].clear();
}
for(int i=1; i<=q; i++) vec[l[i]].pb(i);
DSU.bd();
int cnt = n;
for(int i=n; i>=1; i--){
for(auto nx : adj[i]){
if(nx < i) continue;
if(DSU.con(nx, i)) continue;
++cnt;
int a = DSU.f(nx), b = DSU.f(i);
DSU.mer(a, cnt); DSU.mer(b, cnt);
tree[cnt].pb(a); tree[cnt].pb(b);
}
}
vis = 0; dfs(cnt);
DSU.bd();
cnt = n;
for(int i=1; i<=n; i++) le[i] = ri[i] = val[i];
for(int i=n; i>=1; i--){
for(auto nx : adj[i]){
if(nx < i) continue;
if(DSU.con(nx, i)) continue;
++cnt;
int a = DSU.f(nx), b = DSU.f(i);
DSU.mer(a, cnt); DSU.mer(b, cnt);
le[cnt] = min(le[a], le[b]); ri[cnt] = max(ri[a], ri[b]);
// cout << cnt << ' '<< le[cnt] << ' '<< ri[cnt] << "ab\n";
}
for(auto idx : vec[i]){
int s = DSU.f(sta[idx]);
que[idx][2] = le[s]; que[idx][3] = ri[s];
// cout << idx <<' '<<en[idx] <<' '<<s<< ' '<< le[s] <<' '<<ri[s] <<" ri\n";
}
}
}
solve();
vector<int> A;
for(int i=1; i<=q; i++) A.pb(ans[i]>=1);
return A;
}
