#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=1000100;
const int M=100000010;
int p[N],q[N],sum;
ull ans=1;
bool num[N],lim[N],vis[M];
signed main(){
	int n,m,c,k;cin>>n>>m>>c>>k;
	for(int i=1;i<=n;i++){
		ull a;cin>>a;
		int now=0;
		while(a){
			if(a%2==1) num[now]=1;
			a/=2;
			++now;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>p[i]>>q[i];
		if(num[p[i]]) vis[q[i]]=1;
	}
	for(int i=1;i<=m;i++){
		if(!vis[q[i]]){
			if(!lim[p[i]]) ++sum;
			lim[p[i]]=1;
		}
	}
	if(sum==64&&n==0){
		cout<<"18446744073709551616"<<endl;
		return 0;
	}
	for(int i=1;i<=k;i++){
		if(!lim[i]) ans*=2;
	}
	printf("%llu\n",ans-n);
	return 0;
}