#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
int arr[200005];
int ters[200005];
int komsu[2][200005];
int minst[800005];
int maxst[800005];
int n;
void minstc(int node, int l, int r){
if (l == r) minst[node] = arr[l];
else {
int m = (l+r)/2;
minstc(node*2, l, m);
minstc(node*2+1, m+1, r);
minst[node] = min(minst[node*2], minst[node*2+1]);
}
}
int minstq(int node, int l, int r, int sl, int sr){
if (sl <= l && r <= sr) return minst[node];
else if (r < sl || sr < l) return 1000000000;
else {
int m = (l+r)/2;
return min(minstq(node*2, l, m, sl, sr), minstq(node*2+1, m+1, r, sl, sr));
}
}
void maxstc(int node, int l, int r){
if (l == r) maxst[node] = arr[l];
else {
int m = (l+r)/2;
maxstc(node*2, l, m);
maxstc(node*2+1, m+1, r);
maxst[node] = max(maxst[node*2], maxst[node*2+1]);
}
}
int maxstq(int node, int l, int r, int sl, int sr){
if (sl <= l && r <= sr) return maxst[node];
else if (r < sl || sr < l) return -1000000000;
else {
int m = (l+r)/2;
return max(maxstq(node*2, l, m, sl, sr), maxstq(node*2+1, m+1, r, sl, sr));
}
}
int solve(int s, int e, int L, int R){
if (s < e){
int l = s;
int r = e;
while (l < r){
int m = (l+r+1)/2;
if (minstq(1, 0, n-1, l, m) < L) r = m-1;
else l = m;
}
if (minstq(1, 0, n-1, s, l) >= L && maxstq(1, 0, n-1, l, e) <= R) return 1;
else return 0;
} else {
int l = e;
int r = s;
while (l<r){
int m = (l+r)/2;
if (minstq(1, 0, n-1, m, r) < L) l = m+1;
else r = m;
}
if (minstq(1, 0, n-1, l, s) >= L && maxstq(1, 0, n-1, e, l) <= R) return 1;
else return 0;
}
}
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;
for (int i = 0; i < N; i++) komsu[0][i] = komsu[1][i] = -1;
for (int i = 0; i < X.size(); i++){
if (komsu[0][X[i]] == -1) komsu[0][X[i]] = Y[i];
else komsu[1][X[i]] = Y[i];
if (komsu[0][Y[i]] == -1) komsu[0][Y[i]] = X[i];
else komsu[1][Y[i]] = X[i];
}
int basnode;
for (basnode = 0; basnode < N; basnode++) if(komsu[1][basnode] == -1) break;
arr[0] = basnode; ters[basnode] = 0;
arr[1] = komsu[0][basnode]; ters[komsu[0][basnode]] = 1;
for (int i = 2; i < N; i++){
if (arr[i-2] != komsu[0][arr[i-1]] && komsu[0][arr[i-1]] != -1) arr[i] = komsu[0][arr[i-1]], ters[komsu[0][arr[i-1]]] = i;
else arr[i] = komsu[1][arr[i-1]], ters[komsu[1][arr[i-1]]] = i;
}
//for (int i = 0; i < N; i++) cout << arr[i] << " "; cout << endl;
vector<int> ans(S.size(), 5);
minstc(1, 0, n-1);
maxstc(1, 0, n-1);
for (int i = 0; i < S.size(); i++) ans[i] = solve(ters[S[i]], ters[E[i]], L[i], R[i]);
return ans;
}
