#include<bits/stdc++.h>
#ifndef LOCAL
#include "obstacles.h"
#endif
using namespace std;
#define ll long long
vector<ll>adj[200005];
bool vis[200005];
ll lft[200005][20];
ll mini[200005][20],maxi[200005][20];
ll dep[200005];
void dfs(ll s){
vis[s]=1;
for(auto& u: adj[s]){
if(!vis[u]){
dep[u]=dep[s]+1;
lft[u][0]=s;
mini[u][0]=maxi[u][0]=s;
dfs(u);
}
}
}
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';
adj[u].push_back(v); adj[v].push_back(u);
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(200005),entering(200005);
vector<bool>opened(200005,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);
}
pair<ll,ll> bl(ll u, ll v){
if(dep[u]<dep[v]){
swap(u,v);
}
ll minn=1e18; ll maxx=-1e18;
ll req=dep[u]-dep[v];
for(int i=0;i<=19;i++){
if(req&(1LL<<i)){
maxx=max(maxx,maxi[u][i]); minn=min(minn,mini[u][i]); u=lft[u][i];
}
}
if(u==v)return {minn,maxx};
for(int i=19;i>=0;i--){
if(lft[u][i]==lft[v][i])continue;
maxx=max({maxx,maxi[u][i],maxi[v][i]});
minn=min({minn,mini[u][i],mini[v][i]});
u=lft[u][i],v=lft[v][i];
}
return {min(minn,lft[u][0]),max(maxx,lft[v][0])};
}
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>mink(n+5);
for(int i=0;i<n;i++){
mink[i]=T[i];
if(i!=0){
mink[i]=min(mink[i],mink[i-1]);
}
}
for(int i=0;i<m;i++){
ll l=0,r=n-1;
if(mink[n-1]>H[i]){
reachable[i]=n-1;
}
else if(mink[0]<=H[i]){
reachable[i]=-1;
}
else{
while(l<r){
ll mid=(l+r+1)>>1;
if(mink[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 maxx=-1;
vector<pair<ll,ll> >rows;
for(int i=0;i<n;i++){
if(T[i]>maxx){
rows.push_back({T[i],i}); maxx=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);
}
}
for(int i=0;i<m;i++){
for(int j=0;j<=19;j++){
mini[i][j]=maxi[i][j]=-1;
lft[i][j]=-1;
}
}
for(int i=0;i<m;i++){
if(!vis[i]){
dfs(i);
}
}
for(int j=1;j<=19;j++){
for(int i=0;i<m;i++){
if(lft[i][j-1]==-1)continue;
if(lft[lft[i][j-1]][j-1]==-1)continue;
ll nxt=lft[i][j-1];
lft[i][j]=lft[lft[i][j-1]][j-1];
maxi[i][j]=max(maxi[i][j-1],maxi[nxt][j-1]);
mini[i][j]=min(mini[i][j-1],mini[nxt][j-1]);
}
}
}
bool can_reach(int L, int R, int S, int D){
if(!d.connected(S,D))return 0;
pair<ll,ll> val=bl(S,D);
if(val.first>=L&&val.second<=R)return 1;
return 0;
}
#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
*/
