#include "werewolf.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct dsu
{
int P[400'001];
int cost[400'001];
vi sons[400'001];
int jump[400'001][19];
int cur_v = 200'001;
int pre[400'001];
int max_pre[400'001];
int cur_pre = 0;
dsu()
{
rep(i,400'001)
{
P[i] = i;
jump[i][0] = i;
}
}
int fint(int v)
{
if(P[v] == v) return v;
P[v] = fint(P[v]);
return P[v];
}
void onion(int a, int b, int c)
{
a = fint(a);
b = fint(b);
if(a == b) return;
P[a] = cur_v;
P[b] = cur_v;
cost[a] = c;
cost[b] = c;
cost[cur_v] = c;
jump[a][0] = cur_v;
jump[b][0] = cur_v;
sons[cur_v].pb(a);
sons[cur_v].pb(b);
cur_v++;
}
void dfs(int v)
{
pre[v] = cur_pre++;
max_pre[v] = pre[v];
forall(it,sons[v])
{
dfs(it);
max_pre[v] = max_pre[it];
}
}
void calc_tree()
{
rep2(bit,1,18)
{
rep(i,400'001)
{
jump[i][bit] = jump[jump[i][bit-1]][bit-1];
}
}
rep(i,400'001)
{
if(P[i] == i)
{
dfs(i);
}
}
}
};
struct event
{
int type, x, y1,y2,ind;
bool operator<(const event& other)
{
if(x != other.x) return x < other.x;
return type < other.type;
}
};
const int tree_siz = 1024*1024-1;
int drzewo[tree_siz+1];
int get_sum(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return 0;
if(p1 >= s1 && p2 <= s2) return drzewo[akt];
return get_sum(akt*2,p1,(p1+p2)/2,s1,s2) + get_sum(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}
void upd(int v)
{
drzewo[v] = drzewo[v*2] + drzewo[v*2+1];
if(v != 1) upd(v/2);
}
void change(int ind)
{
drzewo[tree_siz/2+1+ind]++;
upd((tree_siz/2+1+ind)/2);
}
dsu dsu_human;
dsu dsu_wolf;
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R)
{
vector<pair<int,pii>> edges_H;
vector<pair<int,pii>> edges_W;
rep(i,siz(X))
{
edges_H.pb({min(X[i],Y[i]),{X[i],Y[i]}});
edges_W.pb({max(X[i],Y[i]),{X[i],Y[i]}});
}
sort(all(edges_H));
sort(all(edges_W));
reverse(all(edges_H));
forall(it,edges_W)
{
dsu_wolf.onion(it.ss.ff,it.ss.ss,it.ff);
}
forall(it,edges_H)
{
dsu_human.onion(it.ss.ff,it.ss.ss,it.ff);
}
dsu_human.calc_tree();
dsu_wolf.calc_tree();
vector<event> events;
rep(i,siz(S))
{
int beg = S[i];
for(int bit = 18; bit >= 0; bit--)
{
if(dsu_human.cost[dsu_human.jump[beg][bit]] >= L[i])
{
beg = dsu_human.jump[beg][bit];
}
}
if(dsu_human.cost[beg] >= L[i]) beg = dsu_human.jump[beg][0];
int en = E[i];
for(int bit = 18; bit >= 0; bit--)
{
if(dsu_wolf.cost[dsu_wolf.jump[en][bit]] <= R[i])
{
en = dsu_wolf.jump[en][bit];
}
}
if(dsu_wolf.cost[en] <= R[i]) en = dsu_wolf.jump[en][0];
events.pb({1,dsu_human.pre[beg]-1,dsu_wolf.pre[en],dsu_wolf.max_pre[en],i});
events.pb({2,dsu_human.max_pre[beg],dsu_wolf.pre[en],dsu_wolf.max_pre[en],i});
}
rep(i,n)
{
events.pb({0,dsu_human.pre[i],dsu_wolf.pre[i],dsu_wolf.pre[i],-1});
}
sort(all(events));
vi ans(siz(S));
forall(it,events)
{
if(it.type == 0) change(it.y1);
else
{
if(it.type == 1)
{
ans[it.ind] = get_sum(1,0,tree_siz/2,it.y1,it.y2);
}
else
{
if(ans[it.ind] == get_sum(1,0,tree_siz/2,it.y1,it.y2))
{
ans[it.ind] = 0;
}
else
{
ans[it.ind] = 1;
}
}
}
}
return ans;
}
