#include <bits/stdc++.h>
using namespace std;
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
template<class T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; }
template<class T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }
const int N = 1e6 + 5;
int n, m, q;
vi adj[N], g[N], ask[N], S, E, L, R;
int par[N], tin[N], tout[N], num_nodes = 0, timer = 0;
int acs(int u) { return par[u] == u ? u : par[u] = acs(par[u]); }
bool join(int u, int v) {
int x = acs(u);
int y = acs(v);
if (x == y) return false;
g[num_nodes].eb(x);
g[num_nodes].eb(y);
par[x] = par[y] = par[num_nodes] = num_nodes;
++num_nodes;
return true;
}
void dfs(int u) {
tin[u] = ++timer;
for(int v : g[u]) {
dfs(v);
}
tout[u] = timer;
}
int tmp[N];
pair<pii, pii> bound[N];
struct point {
ll x, y;
point(ll x = 0, ll y = 0) : x(x), y(y) {}
bool operator < (const point& o) const {
return x < o.x;
}
};
point P[N];
pair<point, point> rect[N];
void reset() {
num_nodes = n;
timer = 0;
REP(i, 0, n + m) {
g[i].clear();
par[i] = -1;
tin[i] = 0;
tout[i] = 0;
tmp[i] = 0;
}
}
struct query {
int y, id, type;
query(int y = 0, int id = 0, int type = 0) : y(y), id(id), type(type) {}
};
vector<query> eq[N];
ll sum[N];
void reset_dsu(int siz) {
REP(i, 0, siz)
par[i] = i;
}
void process1() {
reset();
reset_dsu(n);
REP(i, 0, q) {
ask[L[i]].eb(i);
}
FORD(u, n - 1, 0) {
for(int v : adj[u]) {
if (v >= u) {
// cerr << u << " " << v << el;
join(u, v);
}
}
for(int id : ask[u]) {
tmp[id] = acs(S[id]);
}
}
dfs(num_nodes - 1);
REP(i, 0, n) {
P[i].x = tin[i];
}
REP(i, 0, q) {
// rect[i].first.x = point(tin[tmp[i]], tout[tmp[i]]);
rect[i].ff.x = tin[tmp[i]];
rect[i].ss.x = tout[tmp[i]];
}
REP(i, 0, q) {
ask[L[i]].clear();
}
}
void process2() {
reset();
reset_dsu(n);
REP(i, 0, q) {
ask[R[i]].eb(i);
}
REP(u, 0, n) {
for(int v : adj[u]) {
if (v <= u)
join(u, v);
}
for(int id : ask[u]) {
tmp[id] = acs(E[id]);
}
}
dfs(num_nodes - 1);
REP(i, 0, n) {
P[i].y = tin[i];
}
REP(i, 0, q) {
// rect[i].first.x = point(tin[tmp[i]], tout[tmp[i]]);
rect[i].ff.y = tin[tmp[i]];
rect[i].ss.y = tout[tmp[i]];
}
REP(i, 0, q)
ask[R[i]].clear();
}
struct BIT {
vector<ll> bit;
BIT(int n) : bit(n + 5, 0) {}
void update(int pos) {
while(pos < sz(bit)) {
bit[pos] += 1;
pos += pos & -pos;
}
}
ll get(int pos) {
ll res = 0;
while(pos) {
res += bit[pos];
pos -= pos & -pos;
}
return res;
}
};
vi check_validity(int N, vi X, vi Y, vi _S, vi _E, vi _L, vi _R) {
n = N;
m = sz(X);
q = sz(_S);
vi ans;
ans.resize(q);
REP(i, 0, m) {
int u = X[i];
int v = Y[i];
adj[u].eb(v);
adj[v].eb(u);
}
S.resize(q), E.resize(q), L.resize(q), R.resize(q);
REP(i, 0, q) {
S[i] = _S[i];
E[i] = _E[i];
L[i] = _L[i];
R[i] = _R[i];
}
process1();
process2();
REP(i, 0, q) {
int x1, y1, x2, y2;
x1 = rect[i].ff.x;
y1 = rect[i].ff.y;
x2 = rect[i].ss.x;
y2 = rect[i].ss.y;
eq[x2].eb(query(y2, i, 1));
eq[x1 - 1].eb(query(y2, i, -1));
eq[x2].eb(query(y1 - 1, i, -1));
eq[x1 - 1].eb(query(y1 - 1, i, 1));
}
sort(P, P + n);
BIT ft(4 * n);
REP(i, 0, n) {
ft.update(P[i].y);
for(auto s : eq[P[i].x]) {
sum[s.id] += s.type * ft.get(s.y);
}
}
REP(i, 0, q) {
if (sum[i]) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}
/*
*/
