#include<queue>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<iomanip>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<utility>
#include<cstring>
#include<stack>
#include<fstream>
#include <sstream>
#include<string>
#include<stdlib.h>
using namespace std;
#define ull unsigned long long
#define gc getchar()
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
inline ull rd(){
    ull x=0; char s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=gc;
    return x;
} ull n,m,c,k,ans,lim,hv;
int main()
{
    n = rd() , m = rd() , c=rd() , k = rd();
    for(int i=1;i<=n;i++)
        hv|=rd();
    for(int i=1;i<=m;i++)
        lim|=1ull<<rd(),rd();
    for(int i=0;i<k;i++)
        ans+= !((lim>>i)&1) || ((hv>>i)&1);
    if(ans==64&&!n)
        puts("18446744073709551616");
    else 
        cout<<(1ull<<ans)-n<<endl;
    return 0;
}

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

#define ull unsigned long long
#define gc getchar()

inline ull rd(){
	ull x=0; char s=gc;
	while(!isdigit(s))s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=gc;
	return x;
} ull n,m,c,k,ans,lim,hv;

int main(){
	n=rd(),m=rd(),c=rd(),k=rd();
	for(int i=1;i<=n;i++)
		hv|=rd(); // 统计每个位是否有 1
	for(int i=1;i<=m;i++)
		lim|=1ull<<rd(),rd(); // 统计有限制的位
	for(int i=0;i<k;i++)
		ans+= !((lim>>i)&1) || ((hv>>i)&1); // 如果当前位有 1, 或者没有限制，那么都可以选
	if(ans==64&&!n)
		puts("18446744073709551616");
	else 
		cout<<(1ull<<ans)-n<<endl;
	return 0;
}

#include using namespace std; int main(){ for(long long i=0;i<=514514;i++){ cout<<"1111111111111111111111111111111111111111111111111"; } return 0; }