#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define PII pair<int,int>
#define fi first
#define se second
#define mk make_pair

#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)

void chkmin(int &x,int y){ if(x>y) x=y;}
void chkmax(int &x,int y){ if(x<y) x=y;}

int read(){
	int s=0,w=1; char c=getchar();
	while(!isdigit(c)){ if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)){ s=(s<<3)+(s<<1)+(c^48); c=getchar();}
	return s*w;
}
void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>9) write(x/10);
	putchar((char)(x%10+'0'));
}
void write_(int x){
	write(x);
	putchar(' ');
}
void writeline(int x){
	write(x);
	puts("");
}

const int N=5e5+5;

int c,n,m,q,a[2005],b[2005],aa[2005],bb[2005];

int f[2005][2005];
int check(){
	if(a[1]<=b[1] && a[n]>=b[m]) return 0;
	if(a[1]>=b[1] && a[n]<=b[m]) return 0;
	if(a[1]==b[1] || a[n]==b[m]) return 0;
	memset(f,0,sizeof f);
	if(a[1]<b[1]){
		f[1][1]=1;
		rep(i,1,n){
			rep(j,1,m){
				if(!f[i][j]) continue;
				if(i<n) if(a[i+1]<b[j]) f[i+1][j]=1;
				if(j<m) if(a[i]<b[j+1]) f[i][j+1]=1;
			}
		}
		return f[n][m];
	}
	else{
		f[1][1]=1;
		rep(i,1,n){
			rep(j,1,m){
				if(!f[i][j]) continue;
				if(i<n) if(a[i+1]>b[j]) f[i+1][j]=1;
				if(j<m) if(a[i]>b[j+1]) f[i][j+1]=1;
			}
		}
		return f[n][m];
	}
}

int ans[N];

int A[N],B[N],AA[N],BB[N];
int check1(){
	int nowx=1,nowy=1;
	while(1){
		if(nowy==m-1) return 1;
		if(nowx==n) return 0;
		if(A[nowx+1]<B[nowy+1]) ++nowx,++nowy;
		else if(A[nowx]<B[nowy+1]) ++nowy;
		else return 0;
	}
}

void solve(){
	rep(i,1,n) A[i]=read();
	rep(i,1,m) B[i]=read();
	
	memcpy(AA,A,sizeof A);
	memcpy(BB,B,sizeof B);
	int tot=0;
	ans[++tot]=check1();
	while(q--){
		memcpy(A,AA,sizeof AA);
		memcpy(B,BB,sizeof BB);
		int kx=read(),ky=read();
		rep(i,1,kx){
			int x=read(),y=read();
			A[x]=y;
		}
		rep(i,1,ky){
			int x=read(),y=read();
			B[x]=y;
		}
		ans[++tot]=check1();
	}
	rep(i,1,tot) write(ans[i]);
}

signed main(){
//	system("fc expand.out expand3.ans");
	
	c=read(),n=read(),m=read(),q=read();
	
	if(c>7){
		solve();
		return 0;
	}
	
	rep(i,1,n) a[i]=read();
	rep(i,1,m) b[i]=read();
	
	memcpy(aa,a,sizeof a);
	memcpy(bb,b,sizeof b);
	int tot=0;
	ans[++tot]=check();
	while(q--){
		memcpy(a,aa,sizeof aa);
		memcpy(b,bb,sizeof bb);
		int kx=read(),ky=read();
		rep(i,1,kx){
			int x=read(),y=read();
			a[x]=y;
		}
		rep(i,1,ky){
			int x=read(),y=read();
			b[x]=y;
		}
		ans[++tot]=check();
	}
	rep(i,1,tot) write(ans[i]);
	
	return 0;
}
/*
3 3 3 3
8 6 9
1 7 4
1 0
3 0
0 2
1 8
3 5
1 1
2 8
1 7

8 3 3 0
2 5 1
3 4 9

*/