WA#15#20

#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,c,k,a,p,q,i,j,x[64],y[64],s,z;
int main()
{
	cin>>n>>m>>c>>k;
	s=k;
	for(i=0;i<n;i++)
	{
	cin>>a;
    for(j=0;a>0;j++,a/=2)
    if(a%2!=0) x[j]++;
	}
	for(i=0;i<m;i++)
	{
	cin>>p>>q;
	if(x[p]==0&&y[p]==0)
	{
	y[p]++;
	s--;
	}
	}
	z=pow(2,s)-n;
	cout<<z;
	return 0;
}