/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int ll
const char nl = '\n';
const int N = 2e5+5;
vector<int> g[N], taze1[N], taze2[N];
vector<pair<int, int>> qqq[N], otv[N];
int par1[N][21], par2[N][21];
int tin1[N], tout1[N];
int tin2[N], tout2[N];
class DisjointSets {
private:
vector<int> parents;
vector<int> sizes;
public:
DisjointSets(int size) : parents(size), sizes(size, 1) {
for (int i = 0; i < size; i++) { parents[i] = i; }
}
/** @return the "representative" node in x's component */
int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
/** @return whether the merge changed connectivity */
bool unite(int x, int y) {
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root) { return false; }
parents[y_root] = x_root;
return true;
}
/** @return whether x and y are in the same connected component */
bool connected(int x, int y) { return find(x) == find(y); }
};
int t1, t2;
int id1[N], id2[N];
int vis[N], vis2[N];
void dfs1(int u) {
id1[t1] = u, vis[u] = 1;
tin1[u] = tout1[u] = t1++;
for (auto i: taze1[u]) {
if (vis[i] == 1)continue;
//assert(vis[i] == 0)
dfs1(i);
tout1[u] = max(tout1[u], tout1[i]);
}
}
void dfs2(int u) {
id2[t2] = u;
vis2[u] = 1;
tin2[u] = tout2[u] = t2++;
for (auto i: taze2[u]) {
if (vis2[i] == 1)continue;
dfs2(i);
tout2[u] = max(tout2[u], tout2[i]);
}
}
void b1(int u, int p) {
par1[u][0] = p;
for (int i = 1; i <= 20; ++i) {
if (par1[u][i-1] == -1)break;
par1[u][i] = par1[par1[u][i-1]][i-1];
}
for (auto i: taze1[u])
b1(i, u);
}
void b2(int u, int p) {
par2[u][0] = p;
for (int i = 1; i <= 20; ++i) {
if (par2[u][i-1] == -1)break;
par2[u][i] = par2[par2[u][i-1]][i-1];
}
for (auto i: taze2[u])
b2(i, u);
}
int calc(int s, int t, int l, int r) {
//return 0;
//cout << pa << " " << t << nl;
//cout << tin1[s] << " " << tout1[s] << nl;
for (int i = tin1[s]; i <= tout1[s]; ++i) {
int x = id1[i];
if (tin2[x] >= tin2[t] && tout2[x] <= tout2[t])return 1;
}
return 0;
}
int fnd1(int u, int x) {
for (int i = 20; i >= 0; --i) {
if (par1[u][i] == -1)continue;
if (par1[u][i] >= x)u = par1[u][i];
}
return u;
}
int fnd2(int u, int x) {
for (int i = 20; i >= 0; --i) {
if (par2[u][i] == -1)continue;
if (par2[u][i] <= x)u = par2[u][i];
}
return u;
}
struct segtree {
vector<int> tree;
int size;
void init(int n) {
size = 1;
while (size < n)size <<= 1;
tree.assign(2*size-1, 0);
}
void add(int i, int x, int lx, int rx) {
if (rx-lx==1) {
tree[x]+=1;
return;
}
int mid = lx+rx>>1;
if (i < mid)add(i, 2*x+1, lx, mid);
else add(i, 2*x+2, mid, rx);
tree[x] = tree[2*x+1]+tree[2*x+2];
}
void add(int i) {
add(i, 0, 0, size);
}
int get(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx)return 0;
if (lx >= l && rx <= r)return tree[x];
int mid = (lx + rx) >> 1;
return get(l, r, 2*x+1, lx, mid)+get(l, r, 2*x+2, mid, rx);
}
int get(int l, int r) {
return get(l, r, 0, 0, size);
}
};
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 q = s.size(), m = sz(x);
for (int i = 0; i < m; ++i) {
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
DisjointSets human(n);
// for (int i = 0; i < n; ++i)
// par1[i] = par2[i] = -1;
vector<int> mark1(n+1);
for (int i = n-1; i >= 0; --i) {
mark1[i] = 1;
for (auto j: g[i]) { // small to large
if (mark1[j]) {
int c = human.find(j);
if (human.unite(i, c)) {
taze1[i].push_back(c);
// par1[c] = i;
}
}
}
}
DisjointSets wolf(n+1);
vector<int> mark2(n+1);
for (int i = 0; i < n; ++i) {
mark2[i] = 1;
for (auto j: g[i]) { // large to small
if (mark2[j]) {
int c = wolf.find(j);
if (wolf.unite(i, c)) {
taze2[i].push_back(c);
// par2[c] = i;
}
}
}
}
memset(par1, -1, sizeof par1);
memset(par2, -1, sizeof par2);
dfs1(0);
dfs2(n-1);
b1(0, -1);
b2(n-1, -1);
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
s[i] = fnd1(s[i], l[i]);
e[i] = fnd2(e[i], r[i]);
//while (par1[s[i]][0] != -1 && par1[s[i]][0] >= l[i]) {
//s[i] = par1[s[i]][0];
//}
//while (par2[e[i]][0] != -1 && par2[e[i]][0] <= r[i]) {
//e[i] = par2[e[i]][0];
//}
if (tin1[s[i]] > 0) {
qqq[tin1[s[i]]-1].push_back({tin2[e[i]], tout2[e[i]]});
otv[tin1[s[i]]-1].push_back({i, -1});
}
qqq[tout1[s[i]]].push_back({tin2[e[i]], tout2[e[i]]});
otv[tout1[s[i]]].push_back({i, 1});
}
segtree st;
st.init(n+1);
for (int i = 0; i < n; ++i) {
st.add(tin2[id1[i]]);
for (int j = 0; j < sz(qqq[i]); ++j) {
auto &qu = qqq[i][j];
auto &aa = otv[i][j];
int sum = st.get(qu.first, qu.second+1);
ans[aa.first] += sum*aa.second;
}
}
for (auto &i: ans)
if (i > 0)i = 1;
return ans;
}
//void solve() {
//int n, m, q; cin >> n >> m >> q;
//vector<int> x(m), y(m);
//for (int i = 0; i < m; ++i)cin >> x[i] >> y[i];
//vector<int> s(q), e(q), l(q), r(q);
//for (int i = 0; i < q; ++i)cin >> s[i] >> e[i] >> l[i] >> r[i];
//vector<int> ans = check_validity(n, x, y, s, e, l, r);
//for (auto i: ans)cout << i << nl;
//}
//int32_t main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
//int t = 1;
//for (int _ = 0; _ < t; ++_) {
//solve();
//}
//return 0;
//}
