#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
int n,cnt,m,c;
unsigned long long k;
int a;
int q,p;
bool f[100];
bool x[100];
int main(){
	scanf("%d%d%d%u",&n,&m,&c,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		for(int j=0;a;j++){
			f[j]|=(a&1);
			a>>=1;
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&p,&q);
		x[p]=1^f[p];
//		cout<<f[p]<<"    "<<x[p]<<endl;
//		cout<<f[p]<<endl; 
	}
	for(int i=0;i<k;i++){
		if(x[i]){
			cnt++;
		}
	}
//	cout<<cnt<<endl;
	k=k-cnt;
//	cout<<f[1]<<endl;
	if(k==64)return !printf("18446744073709551616");
	else cout<<(1<<k)-n;
	return 0;
}