#include<bits/stdc++.h>
#ifndef LOCAL
#include "obstacles.h"
#endif
using namespace std;
#define ll long long
struct DSU{
vector<ll>fa,siz;
void init(ll n){
fa.resize(n+5); siz.resize(n+5);
for(int i=0;i<=n;i++)fa[i]=i,siz[i]=1;
}
ll rt(ll x){
if(fa[x]==x)return x;
return fa[x]=rt(fa[x]);
}
void unite(ll u, ll v){
// cout<<"Add edge "<<u<<" "<<v<<'\n';
u=rt(u); v=rt(v);
if(u==v)return;
if(siz[u]<siz[v])swap(u,v);
siz[u]+=siz[v]; fa[v]=u;
}
bool connected(ll u, ll v){
return (rt(u)==rt(v));
}
}d;
struct Set{
vector<ll>fa,siz,l,r;
vector<set<ll> >hv;
void init(ll n){
siz.resize(n+5); fa.resize(n+5); l.resize(n+5);
r.resize(n+5); hv.resize(n+5);
for(int i=0;i<=n;i++){
siz[i]=1; fa[i]=i; l[i]=i; r[i]=i;
}
}
void add(ll x){
// cout<<"Inserted "<<x<<'\n';
hv[x].insert(x);
}
ll rt(ll x){
if(fa[x]==x)return x;
return fa[x]=rt(fa[x]);
}
void unite(ll u, ll v){
// cout<<"Join "<<u<<" "<<v<<'\n';
u=rt(u); v=rt(v);
if(siz[u]<siz[v])swap(u,v);
siz[u]+=siz[v]; fa[v]=u;
l[u]=min(l[u],l[v]); r[u]=max(r[u],r[v]);
if(hv[u].size()==0||hv[v].size()==0){
}
else{
if(u<v){
d.unite(*hv[u].rbegin(),*hv[v].begin());
}
else{
// cout<<u<<" "<<v<<'\n';
// cout<<"hi "<<*hv[v].rbegin()<<" "<<*hv[u].begin()<<'\n';
d.unite(*hv[v].rbegin(),*hv[u].begin());
}
}
for(auto& k: hv[v])hv[u].insert(k);
}
void del(ll x){
ll r=rt(x);
if(hv[r].empty())return;
if(*hv[r].rbegin()<x)return;
ll bruh=*hv[r].lower_bound(x);
if(bruh!=x)return;
hv[r].erase(x);
}
}st;
ll n,m;
vector<ll>reachable(m+5),entering(m+5);
vector<bool>opened(m+5,false);
void modify(ll x, ll m, bool add){
if(add)st.add(x);
if(x==0){
if(!opened[x+1]){
}
else{
st.unite(x,x+1);
}
}
else if(x==m-1){
if(opened[x-1])st.unite(x,x-1);
}
else{
if(opened[x+1])st.unite(x,x+1);
if(opened[x-1])st.unite(x,x-1);
}
opened[x]=1;
}
void erase(ll x){
// cout<<"Erased "<<x<<'\n';
st.del(x);
}
void initialize(vector<int> T, vector<int> H){
n=T.size(); m=H.size();
st.init(m); d.init(m);
// T[i]>H[j]: can step on
vector<ll>mini(n+5);
for(int i=0;i<n;i++){
mini[i]=T[i];
if(i!=0){
mini[i]=min(mini[i],mini[i-1]);
}
}
for(int i=0;i<m;i++){
ll l=0,r=n-1;
if(mini[n-1]>H[i]){
reachable[i]=n-1;
}
else if(mini[0]<=H[i]){
reachable[i]=-1;
}
else{
while(l<r){
ll mid=(l+r+1)>>1;
if(mini[mid]>H[i])l=mid;
else r=mid-1;
}
reachable[i]=l;
}
}
// row: T array, column, H array
// T[i]>H[j]: can step on
ll maxi=-1;
vector<pair<ll,ll> >rows;
for(int i=0;i<n;i++){
if(T[i]>maxi){
rows.push_back({T[i],i}); maxi=T[i];
}
}
vector<ll>arrays[rows.size()+5];
vector<ll>dels[rows.size()+5];
for(int i=0;i<m;i++){
if(reachable[i]==-1)continue;
ll req=reachable[i]+1;
// when rows[l].second>=req
if(req>rows[rows.size()-1].second)continue;
ll l=0,r=rows.size()-1;
while(l<r){
ll mid=(l+r)>>1;
if(rows[mid].second>=req)r=mid;
else l=mid+1;
}
dels[l].push_back(i);
}
for(int i=0;i<m;i++){
if(H[i]>=rows[rows.size()-1].first){
continue;
}
ll l=0,r=rows.size()-1;
while(l<r){
ll mid=(l+r)>>1;
if(rows[mid].first>H[i])r=mid;
else l=mid+1;
}
arrays[l].push_back(i);
}
// for(auto& u: arrays[0]){
// modify(u,m,1);
// }
// for(int i=1;i<(int)rows.size();i++){
// for(auto& u: dels[i]){
// erase(u);
// }
// for(auto& u: arrays[i]){
// modify(u,m,0);
// }
// }
}
bool can_reach(int L, int R, int S, int D){
return d.connected(S,D);
}
#ifdef LOCAL
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
/*
3 4
2 1 3
1 1 2 0
2
0 3 1 3
0 3 0 1
*/
