#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,c,k,p,q,ans;
unsigned long long int have[128];
int main()
{
	
	cin>>n>>m>>c>>k;
	if(k==64 and n==0)
	{
		cout<<"18446744073709551616";//只要先输出一个(unsigned long long)-1 再加上 1 就行了
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		unsigned long long tmp;int cnt=0;
		cin>>tmp;
		while(tmp)
		{
			if(tmp%2) have[cnt]=1;
			tmp/=2;cnt++;
		}
	}
	for(int i=1;i<=m;i++)
	{
		cin>>p>>q;
		if(have[p]==0) have[p]=-1;
	}
	for(int i=0;i<k;i++)
	{
		if(have[i]==-1) ans++;
	}
	ans=1<<(k-ans);
	cout<<ans-n;
	return 0;
}