#include "obstacles.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
int N, M;
struct Dsu{
vector<int> v, maxT, minT, maxH, minH;
void build() {
v.resize(M, 1);
}
int findrep(int n) {
if(v[n] > 0) return n;
int x = findrep(-v[n]);
v[n] = -x;
return x;
}
void unite(int a, int b) {
a = findrep(a);
b = findrep(b);
if(a == b) return;
if(v[a] > v[b]) swap(a, b);
v[b] += v[a];
v[a] = -v[b];
}
};
vector<int> tmm, tM;
void bulid(int v, int l, int r, vector<int> &V) {
if(l == r) {
tmm[v] = V[l];
tM[v] = V[l];
return;
}
int m = (l+r)/2;
bulid(v*2, l, m, V);
bulid(v*2+1, m+1, r, V);
tmm[v] = min(tmm[v*2], tmm[v*2+1]);
tM[v] = max(tM[v*2], tM[v*2+1]);
}
int querym(int v, int l, int r, int ql, int qr) {
if(ql > qr) return INT_MAX;
if(ql == l && qr == r) return tmm[v];
int m = (l+r)/2;
return min(
querym(v*2, l, m, ql, min(m, qr)),
querym(v*2+1, m+1, r, max(m+1, ql), qr)
);
}
int queryM(int v, int l, int r, int ql, int qr) {
if(ql > qr) return -1;
if(ql == l && qr == r) return tM[v];
int m = (l+r)/2;
return max(
queryM(v*2, l, m, ql, min(m, qr)),
queryM(v*2+1, m+1, r, max(m+1, ql), qr)
);
}
vector<int> group;
vector<int> lg, rg;
map<int, int> mph; //per ogni umidità, la massima T raggiungibile
vector<int> HH;
void initialize(std::vector<int> T, std::vector<int> H) {
N = T.size();
M = H.size();
tmm.resize(M*4+5);
tM.resize(M*4+5);
bulid(1, 0, M-1, H);
////////////////////////////////
group.resize(M, -1);
int G = -1;
bool status = 0;
for(int i=0; i<M; i++) {
if(!status && T[0] > H[i]) {
G++;
group[i] = G;
status = 1;
lg.push_back(i-1);
}
else if(T[0] > H[i]) {
group[i] = G;
}
else {
if(i > 0 && group[i-1] != -1) rg.push_back(i);
status = 0;
}
}
if(status) rg.push_back(M);
//////////////////////////////////
//calcolo mpH
vector<int> idh(M);
iota(all(idh), 0);
sort(all(idh), [&](int i, int j){return H[i] > H[j];});
int t = 0;
int hight = -1;
for(int i: idh) {
int h = H[i];
while(t < T.size() && T[t] > h) {
t++;
hight = max(hight, T[t-1]);
}
mph[h] = hight;
}
HH.swap(H);
}
bool can_reach(int L, int R, int S, int D) {
if(D == S) return 1;
if(S > D) swap(D, S);
L = max(L, lg[group[S]]+1);
R = min(R, rg[group[D]]-1);
if(group[S] == group[D]) return 1;
int gs = group[S], gd = group[D];
int h1 = querym(1, 0, M-1, L, rg[gs]-1);
int h2 = querym(1, 0, M-1, lg[gd]+1, R);
int h = queryM(1, 0, M-1, L, R);
if(mph[h1] > h && mph[h2] > h) return 1;
return 0;
}
#ifdef MARCO
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> T(N), H(M);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &T[i]));
for (int i = 0; i < M; i++)
assert(1 == scanf("%d", &H[i]));
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> L(Q), R(Q), S(Q), D(Q);
for (int i = 0; i < Q; i++)
assert(4 == scanf("%d %d %d %d", &L[i], &R[i], &S[i], &D[i]));
fclose(stdin);
std::vector<bool> A(Q);
initialize(T, H);
for (int i = 0; i < Q; i++)
A[i] = can_reach(L[i], R[i], S[i], D[i]);
for (int i = 0; i < Q; i++)
if (A[i])
printf("1\n");
else
printf("0\n");
fclose(stdout);
return 0;
}
#endif
