#include<bits/stdc++.h>
using namespace std;

unsigned long long n,m,c,k,a=0,b=0,sum=1;

int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&c,&k);
	if(n==0&&m==0&&k==64)printf("1844674407370955161");
	for(int i=1;i<=n;++i)
	{
		unsigned long long temp;
		scanf("%lld",&temp);
		a|=temp;
	}
	for(int i=1;i<=m;++i)
	{
		unsigned long long p,q;
		scanf("%lld%lld",&p,&q);
		b|=(1<<p);
	}
	for(int i=1;i<=k;++i)if((a&((unsigned long long)1<<i))!=0||(b&((unsigned long long)1<<i))!=1)sum<<=1;
	printf("%lld",sum-n);
	return 0;
}