#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,c,k,a,p[N],q[N];
unsigned long long pow_(int x)
{
	int ans=1;
	for(int i=1;i<=x;i++)
		ans*=2;
	return ans;
}
int main()
{
	// freopen("zoo.in","r",stdin);
	// freopen("zoo.out","w",stdout); 
	cin>>n>>m>>c>>k;
	unsigned long long cnt=pow_(k);
	bool f[70]={0},f1[N]={0}; 
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		for(int j=0;a;j++,a>>=1)
			if(a&1)
				f[j]=1;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>p[i]>>q[i];
		f1[p[i]]=1;
	}
	for(int i=1;i<=k;i++)
		if(!f[i]&&f1[i])
			cnt-=pow_(i);
	cout<<cnt-n<<endl;
	return 0;
}