#include<iostream>
#include<fstream>
using namespace std;
unsigned long long a[1000010];
unsigned long long x=0,y=1;
int main() {
//	freopen("zoo.in","r",stdin);
//	freopen("zoo.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	int c,k;
	cin>>c>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++) {
		int p,q;
		cin>>p>>q;
		if(x/(1<<p)%2==0)
			x+=(1<<p);
	}
	for(int i=1;i<=n;i++) 
		x&=~a[i];
//	cout<<x<<' ';
	x=~x;
	if(x==0xffffffffffffffff&&k==64) {
		cout<<0xffffffffffffffff-n+1;
		return 0;
	}
	while(k--) {
		y*=x%2+1;
//		cout<<x%2+1<<' ';
		x>>=1;
//		cout<<y<<'\n';
	}
//	cout<<0xffffffffffffffff;
	cout<<y-n;
	return 0;
}