#ifdef dzy
	#pragma GCC optimize(2,3,"Ofast","inline")
#endif
#include<bits/stdc++.h>
using namespace std;
#define max_n 500002
#define inf 2e9
int SID;
int n;
int m;
int TID,ca;
int a[max_n+2];
int b[max_n+2];
int qn;
int qm;
struct Q{int x,wf;}que[max_n*2+2];
int api[max_n+2];
int asi[max_n+2];
int bpa[max_n+2];
int bsa[max_n+2];
int pre[max_n+2];
int suc[max_n+2];
int pp[max_n+2];
int ss[max_n+2];
int askans(){
	if(a[1]==b[1]||a[n]==b[n]||((a[1]<b[1])!=(a[n]<b[m])))return 0;
	bool fan=false,res=true;
	if(a[1]>b[1]){
		for(int i=1;i<=n;++i)a[i]=-a[i];
		for(int i=1;i<=m;++i)b[i]=-b[i];
		fan=true;
	}
	api[0]=asi[n+1]=inf;
	bpa[0]=bsa[m+1]=-inf;
	for(int i=1;i<=n;++i)api[i]=min(api[i-1],a[i]);
	for(int i=n;i>=1;--i)asi[i]=min(asi[i+1],a[i]);
	for(int i=1;i<=m;++i)bpa[i]=max(bpa[i-1],b[i]);
	for(int i=m;i>=1;--i)bsa[i]=max(bsa[i+1],b[i]);
	for(int i=1;i<=n&&res;++i){
		if(a[i]>=bpa[m])res=false;
	}
	for(int i=1;i<=m&&res;++i){
		if(api[n]>=b[i])res=false;
	}
	if(!res){
		if(fan){
			for(int i=1;i<=n;++i)a[i]=-a[i];
			for(int i=1;i<=m;++i)b[i]=-b[i];
		}
		return 0;
	}
	for(int i=1,pos,bpi=inf;i<=m;++i){
		pos=0;
		if(b[i]<bpi){
			for(int l=1,r=n,mid;l<=r;){
				if(api[mid=(l+r)>>1]>=b[i]){pos=mid; l=mid+1;}
				else r=mid-1;
			}
			bpi=b[i];
		}
		pre[i]=pos;
	}
	for(int i=m,pos,bsi=inf;i>=1;--i){
		pos=n+1;
		if(b[i]<bsi){
			for(int l=1,r=n,mid;l<=r;){
				if(asi[mid=(l+r)>>1]>=b[i]){pos=mid; r=mid-1;}
				else l=mid+1;
			}
			bsi=b[i];
		}
		suc[i]=pos;
	}
	pp[0]=0;
	for(int i=1;i<=m+1;++i)pp[i]=max(pp[i-1],pre[i]);
	ss[m+1]=n+1;
	for(int i=m;i>=0;--i)ss[i]=min(ss[i+1],suc[i]);
	for(int i=1,pos,apa=-inf;i<=n&&res;++i){
		if(a[i]<=apa)continue;
		apa=a[i];
		pos=0;
		for(int l=1,r=m,mid;l<=r;){
			if(a[i]>=bpa[mid=(l+r)>>1]){pos=mid; l=mid+1;}
			else r=mid-1;
		}
		if(pos>=1&&i<=pp[pos]){res=false; break;}
	}
	for(int i=n,pos,asa=-inf;i>=1&&res;--i){
		if(a[i]<=asa)continue;
		asa=a[i];
		pos=m+1;
		for(int l=1,r=m,mid;l<=r;){
			if(a[i]>=bsa[mid=(l+r)>>1]){pos=mid; r=mid-1;}
			else l=mid+1;
		}
		if(pos<=m&&i>=ss[pos]){res=false; break;}
	}
	if(fan){
		for(int i=1;i<=n;++i)a[i]=-a[i];
		for(int i=1;i<=m;++i)b[i]=-b[i];
	}
	return res;
}
int main(){
	#ifdef dzy
	freopen("P9870_3.in","r",stdin);
//	freopen("P9870_3.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m); TID=0;
	for(int i=1;i<=n;++i)scanf("%d",a+i);
	for(int i=1;i<=m;++i)scanf("%d",b+i);
	for(int i=n+1;i<=max_n;++i)a[i]=inf;
	for(int i=m+1;i<=max_n;++i)b[i]=-inf;
	printf("%d",askans());
	for(ca=1;ca<=TID;++ca){
		scanf("%d%d",&qn,&qm);
		for(int i=1,x,w;i<=qn;++i){
			scanf("%d%d",&x,&w);
			que[i]=(Q){x,a[x]}; a[x]=w;
		}
		for(int i=1,x,w;i<=qm;++i){
			scanf("%d%d",&x,&w);
			que[i+qn]=(Q){x,b[x]}; b[x]=w;
		}
		printf("%d",askans());
		for(int i=1;i<=qn;++i)a[que[i].x]=que[i].wf;
		for(int i=qn+1;i<=qn+qm;++i)b[que[i].x]=que[i].wf;
	}
	printf("\n");
	return 0;
}