#include<iostream>
#include<cstdio>
#include<string>
#define ull unsigned long long
using namespace std;

inline bool rdiw(ull a,int i)//返回a的第i位 
{
	return a&(1ull<<i);
}

inline void wdiw(ull &a,int i,int v)//把a的第i位改为v 
{
	a=(v)? (a|(1ull<<i)):(a=a&(~(1ull<<i)));
}

ull s1,s2;//s1第pi位为1表示“有园中动物的第pi位为1且pi在要求中”，s2第pi位为1表示“pi在要求中”。 
int n,m,c,k;
int tp,tq;//即pi与qi。 
int a[1000006];
ull ans=1;       //须注意，ans表示园中所需饲料总共可以饲养几种动物（包含园中动物） 。 
int main()
{
	scanf("%d%d%d%d",&n,&m,&c,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)//前面有对s2的解释，不再赘述。 
	{
		scanf("%d%d",&tp,&tq);
		wdiw(s2,tp,1);
	}
	
	for(int i=1;i<=n;i++)//a[i]&s2是找a[i]号动物中在要求中的那几位。 
		s1=s1|(a[i]&s2);//此处更新s1的值。 
	
	for(int i=0;i<k;i++)
	{
		if(!(rdiw(s2,i) && !rdiw(s1,i)))//通过列了张表，推出当s2的第i位=1且s1的第i位为0时，所有能饲养的动物的第i位都只能为0（一种选择）。 
			ans*=2;                     //而其他情况则是能饲养的动物的第i位为0或1（有两种选择）。 
	}//乘法原理求方案数。 
	
	printf("%lld",ans-n);
	return 0;
}

自己看注释