#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200000;
struct Edge{
int a, b, c;
bool operator <(const Edge &x){
return c < x.c;
}
};
struct DSU{
int n;
int par[MAXN+5];
int label[MAXN+5];
int sz[MAXN+5];
DSU(int g){
n = g;
for(int i=1; i<=n; i++){
par[i] = i;
label[i] = i;
sz[i] = 1;
}
}
int root(int x){ return (par[x] == x ? x : par[x] = root(par[x])); }
void povezi(int a, int b, int lab){
if(sz[a] < sz[b]) swap(a, b);
label[a] = lab;
sz[a] += sz[b];
par[b] = a;
}
};
const int LOG = 20;
struct PMST{
int n;
vector <pair <int, int>> graf[2*MAXN+5];
int L[2*MAXN+5];
int R[2*MAXN+5];
int val[2*MAXN+5];
int par[2*MAXN+5][LOG+1];
int niz[MAXN+5];
int tn = 0;
void dfs(int v, int p, int w){
val[p] = w;
par[v][0] = p;
for(int j=1; j<=LOG; j++) par[v][j] = par[par[v][j-1]][j-1];
L[v] = 2*MAXN+5;
R[v] = 0;
for(auto c : graf[v]){
dfs(c.first, v, c.second);
L[v] = min(L[v], L[c.first]);
R[v] = max(R[v], R[c.first]);
}
if(!graf[v].size()){
tn++;
L[v] = R[v] = tn;
niz[tn] = v;
}
}
};
PMST tree1, tree2;
int l1[MAXN+5];
int r1[MAXN+5];
int l2[MAXN+5];
int r2[MAXN+5];
int gde[MAXN+5];
int dizi_max(int v, int lm){
for(int j=LOG; j>=0; j--) if(tree1.val[tree1.par[v][j]] <= lm) v = tree1.par[v][j];
return v;
}
int dizi_min(int v, int lm){
for(int j=LOG; j>=0; j--) if(tree2.val[tree2.par[v][j]] >= lm) v = tree2.par[v][j];
return v;
}
vector <int> queries[MAXN+5];
int bit[MAXN+5];
void addbit(int x){
while(x <= MAXN){
bit[x]++;
x += x & -x;
}
}
int getbit(int x){
int res = 0;
while(x){
res += bit[x];
x -= x & -x;
}
return res;
}
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) {
int m = X.size();
vector <Edge> e1, e2;
for(int i=0; i<m; i++){
int a = X[i] + 1;
int b = Y[i] + 1;
e1.push_back({a, b, max(a, b)});
e2.push_back({a, b, min(a, b)});
}
sort(e1.begin(), e1.end());
sort(e2.begin(), e2.end());
reverse(e2.begin(), e2.end());
int n = N;
DSU dsu1(n);
DSU dsu2(n);
int lab1 = n;
int lab2 = n;
for(auto edge : e1){
int a = edge.a;
int b = edge.b;
int c = edge.c;
int a1 = dsu1.root(a);
int b1 = dsu1.root(b);
if(a1 == b1) continue;
lab1++;
tree1.graf[lab1].push_back({dsu1.label[a1], c});
tree1.graf[lab1].push_back({dsu1.label[b1], c});
dsu1.povezi(a1, b1, lab1);
}
tree1.n = lab1;
for(auto edge : e2){
int a = edge.a;
int b = edge.b;
int c = edge.c;
int a1 = dsu2.root(a);
int b1 = dsu2.root(b);
if(a1 == b1) continue;
lab2++;
tree2.graf[lab2].push_back({dsu2.label[a1], c});
tree2.graf[lab2].push_back({dsu2.label[b1], c});
dsu2.povezi(a1, b1, lab2);
}
tree2.n = lab2;
tree1.dfs(lab1, 0, 10*MAXN);
cout << endl;
tree2.dfs(lab2, 0, 0);
vector <int> soln;
int qrs = S.size();
for(int i=0; i<qrs; i++) soln.push_back(0);
for(int i=0; i<qrs; i++){
swap(S[i], E[i]);
S[i]++;
E[i]++;
L[i]++;
R[i]++;
int v = dizi_max(S[i], R[i]);
l1[i] = tree1.L[v];
r1[i] = tree1.R[v];
v = dizi_min(E[i], L[i]);
l2[i] = tree2.L[v];
r2[i] = tree2.R[v];
queries[l2[i]-1].push_back(-(i+1));
queries[r2[i]].push_back(i+1);
}
for(int i=1; i<=n; i++){
gde[tree1.niz[i]] = i;
}
for(int i=1; i<=n; i++){
tree1.niz[i] = gde[tree1.niz[i]];
tree2.niz[i] = gde[tree2.niz[i]];
}
for(int i=1; i<=n; i++){
addbit(tree2.niz[i]);
for(auto ind : queries[i]){
int kf = 1;
if(ind < 0){
kf = -1;
ind = -ind;
}
soln[ind-1] += kf*getbit(r1[ind-1]);
soln[ind-1] -= kf*getbit(l1[ind-1] - 1);
}
}
for(int i=0; i<qrs; i++) if(soln[i] > 0) soln[i] = 1;
return soln;
}
