RT

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull n,m,k,c,a,p,l,q,ans=1,t=1,i,j;bool g[69];
ull read(){
	ull x=0;
	char s=getchar();
	while(!isdigit(s))s=getchar();
	while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return x;
}
int main()
{
	cin>>n>>m>>c>>k;
	for(i=1;i<=n;i++)
	{
		a=read();
		for(j=0;a!=0;j++)
		{
			if(a%2==1) g[j]=true;
			a/=2;
		}
	}
	for(i=1;i<=m;i++)
	{
		p=read();q=read();
		if(g[p]==false) l++;
	}
	for(i=1;i<=k-l;i++) t*=2;
	if(k==64&&n==0)
	{
		cout<<"18446744073709551616";
		return 0;
	}
	cout<<t-n;
	return 0;
}