#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x) (std::isinf(x))
#define IS_NAN(x) (std::isnan(x))
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5 + 5;
const int LOG = 20;
const int INF = 1e18;
int n, m, q; vector<int> x, y, s, e, l, r; vector<int> g[MAXN << 1];
vector<int> gmax[MAXN << 1], gmin[MAXN << 1];
int inpmax[MAXN << 1], outmax[MAXN << 1], inpmin[MAXN << 1], outmin[MAXN << 1];
int comparemax[MAXN], comparemin[MAXN], cntmax = 0, cntmin = 0;
int parmax[MAXN << 1], parmin[MAXN << 1], sparsemax[LOG][MAXN << 1], sparsemin[LOG][MAXN << 1];
vector<pair<int, int>> upper[MAXN], lower[MAXN];
void DFSMax(int u, int p = -1) {
inpmax[u] = ++cntmax;
FORE(it, gmax[u]) if((*it) != p) {
sparsemax[0][(*it)] = u; DFSMax((*it), u);
}
outmax[u] = cntmax;
}
void DFSMin(int u, int p = -1) {
inpmin[u] = ++cntmin; FORE(it, gmin[u]) if((*it) != p) {
sparsemin[0][(*it)] = u; DFSMin((*it), u);
}
outmin[u] = cntmin;
}
int getmax(int u) { return (parmax[u] == u ? u : parmax[u] = getmax(parmax[u])); }
int getmin(int u) { return (parmin[u] == u ? u : parmin[u] = getmin(parmin[u])); }
void updatemax(int idx) {
cntmax++; comparemax[cntmax] = idx;
int u = getmax(idx); parmax[u] = cntmax; gmax[cntmax].push_back(u);
gmax[u].push_back(cntmax); FORE(it, g[idx]) if((*it) >= idx) {
int root = getmax(*it); if(root != cntmax) {
gmax[cntmax].push_back(root); gmax[root].push_back(cntmax);
parmax[root] = cntmax;
}
}
}
void updatemin(int idx) {
cntmin++; comparemin[cntmin] = idx;
int u = getmin(idx); parmin[u] = cntmin; gmin[cntmin].push_back(u);
gmin[u].push_back(cntmin); FORE(it, g[idx]) if((*it) <= idx) {
int root = getmin(*it); if(root != cntmin) {
gmin[cntmin].push_back(root); gmin[root].push_back(cntmin);
parmin[root] = cntmin;
}
}
}
bool checkminDsuTree(int u, int v) {
return (inpmin[v] <= inpmin[u] && outmin[u] <= outmin[v]);
}
bool checkmaxDsuTree(int u, int v) {
return (inpmax[v] <= inpmax[u] && outmax[u] <= outmax[v]);
}
pair<int, int> liftmax(int u, int val) {
FORD(i, LOG - 1, 0) if(checkmaxDsuTree(u, sparsemax[i][u]) &&
comparemax[sparsemax[i][u]] >= val) u = sparsemax[i][u];
return make_pair(inpmax[u], outmax[u]);
}
pair<int, int> liftmin(int u, int val) {
FORD(i, LOG - 1, 0) if(checkminDsuTree(u, sparsemin[i][u]) &&
comparemin[sparsemin[i][u]] <= val) u = sparsemin[i][u];
return make_pair(inpmin[u], outmin[u]);
}
struct queryanswer { pair<int, int> left, right; };
struct rectangle { int u, v, x, y; };
struct FenwickTree {
int tree[MAXN]; void update(int idx, int val) {
for(; idx <= MAXN; idx += (idx & -idx)) tree[idx] += val;
}
int query(int idx) {
int sum = 0; for(; idx >= 1; idx -= (idx & -idx)) sum += tree[idx];
return sum;
}
} bit;
struct query { int x, y, z, t; query() {}; };
struct rectanglequery {
int x, y, idx;
};
bool cmp(const rectanglequery& left, const rectanglequery& right) {
if(left.x != right.x) return left.x < right.x;
else {
if(left.idx != right.idx) return left.idx < right.idx;
return left.y < right.y;
}
}
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 = (int)X.size(); q = (int)S.size(); vector<int> res(q);
REP(i, m) { g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); }
REP(i, (n << 1)) parmax[i] = parmin[i] = i;
cntmax = cntmin = n - 1; FORD(i, n - 1, 0) updatemax(i); REP(i, n) updatemin(i);
int root = cntmax; cntmax = 0; cntmin = 0;
DFSMax(root); DFSMin(root);
FOR(i, 1, LOG - 1) REP(j, (n << 1)) {
sparsemax[i][j] = sparsemax[i - 1][sparsemax[i - 1][j]];
sparsemin[i][j] = sparsemin[i - 1][sparsemin[i - 1][j]];
}
int idxquery = 0; queryanswer u; rectangle queryRec; vector<rectangle> queries; REP(i, q) {
u.left = liftmax(S[i], L[i]); u.right = liftmin(E[i], R[i]);
queryRec.u = u.left.first; queryRec.v = u.right.first;
queryRec.x = u.left.second; queryRec.y = u.right.second;
queries.push_back(queryRec);
}
vector<pair<int, int>> points; REP(i, n) points.push_back({inpmax[i], inpmin[i]});
rectanglequery cur_query;
vector<rectanglequery> queriesrec; int cnt_query = 0; vector<query> combine; REP(i, q) {
combine.push_back(query()); combine.back().x = cnt_query; combine.back().y = cnt_query + 1;
combine.back().z = cnt_query + 2; combine.back().t = cnt_query + 3;
cur_query.x = queries[i].x; cur_query.y = queries[i].y; cur_query.idx = cnt_query++;
queriesrec.push_back(cur_query); cur_query.x = queries[i].x; cur_query.y = queries[i].v - 1;
cur_query.idx = cnt_query++; queriesrec.push_back(cur_query); cur_query.x = queries[i].u - 1;
cur_query.y = queries[i].y; cur_query.idx = cnt_query++; queriesrec.push_back(cur_query);
cur_query.x = queries[i].u - 1; cur_query.y = queries[i].v - 1; cur_query.idx = cnt_query++;
queriesrec.push_back(cur_query);
}
FORE(it, points) queriesrec.push_back({(*it).first, (*it).second, -1});
vector<int> answerqueries((int)queriesrec.size());
sort(ALL(queriesrec), cmp); FORE(it, queriesrec) {
if((*it).idx == -1) bit.update((*it).y, 1);
else answerqueries[(*it).idx] = bit.query((*it).y);
}
REP(i, q) {
int diff = answerqueries[combine[i].x] - answerqueries[combine[i].y] -
answerqueries[combine[i].z] + answerqueries[combine[i].t];
if(diff > 0) res[i] = 1;
}
return res;
}
