rt

#include<bits/stdc++.h>
using namespace std ;
#define int unsigned long long 
int read(){
	int ans = 0 , f = 1 ;char ch = getchar() ;
	while(!isdigit(ch)){if(ch == '-') f = -1 ; ch = getchar() ; }
	while(isdigit(ch)){ans = ans * 10 + (ch ^ '0') ; ch = getchar() ; }
	return ans * f ;
}
const int maxn = 1001000 ; 
int a[maxn] ; 
int sur[70] , wan[70] ; 
//sur是动物圆已经给这一位买了
//wan是这一位需要买
int p[maxn]; 
int ans ; 
#undef int 
int main(){
//	freopen("test.in" , "r" , stdin) ; 
//	freopen("test.out" , "w"  , stdout) ; 
#define int unsigned long long 
	int n = read() , m = read() , c = read() , k = read() ; 
	if(n ==0 && m == 0 && k == 64){
        printf("18446744073709551616");
        return 0;
    }
	for(int i = 1 ; i <= n ; i++)
		scanf("%ull" , &a[i]) ; 
	for(int i = 1; i <= m; i++){
		p[i] = read() ; wan[p[i]] = 1; 
		int q = read() ;
	}
	for(int i = 1; i <= n ; i++){
		for(int j = 0 ; j < k ; j++ ){
			if(sur[j])
				continue ; 
			if(1 << j & a[i] && wan[j])
				sur[j] = 1 ; 
		}
	}
	int ans = 1 ; 
	for(int i = 0 ; i < k ; i++){
		if(sur[i] || !wan[i])//如果这一位已经买了或者根本不需要买的话
			ans *= 2 ; 
	}
	ans -= n ;
	cout << ans ; 
	return 0 ;
}