#include<iostream>
#include<cstdio>
#include<cmath>
#include<bitset>
#define ll long long
using namespace std;
int n,m,k,c,p,q;
ll a[1000010],summ=0,ans;
bool v[70],t[70];
char s[70];

int main()
{
	int len;
	cin>>n>>m>>c>>k;
	
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		int x=a[i];
		int len=0,cnt=0;
		while(x)
		{
			len++;
			x/=2;
		}
		x=a[i];
		while(x)
		{
			cnt++;
			if(x%2==1)
			{
				v[cnt-1]=1;
			}
			x/=2;
		}
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&p,&q);
		t[p]=1;
	}
	if(k==64&&n==0){
		printf("18446744073709551616\n");
		return 0;
	}
	int s1=0,s2=0;
	for(int i=0;i<k;i++)
	{
		if(v[i]&&t[i])s1++;
		if(!v[i]&&t[i])s2++;
	}
	ans=k-s2;
	summ=1;
	for(int i=1;i<=ans;i++)summ*=2;
	
	summ-=(ll)n;
	printf("%lld ",summ);

	return 0;
}

/*
3 3 5 4
1 4 6
0 3
2 4
2 5

13

2 2 4 3
1 2
1 3
2 4

2
*/