#include <bits/stdc++.h>
#define st first
#define nd second
#define int unsigned long long
#define MP make_pair
#define ll long long
#define allx(a) a.begin(),a.end()
#define ally(a) a.rbegin(),a.rend()
#define pii pair<int,int>
#define piii pair<pair<int,int> >
#define pll pair<ll,ll>
#define plll pair<ll,pl >
#define RE cout<<"Ha Ha , you have an RE";
using namespace std;
inline int pow(int x,int y){
    if(y<2)return max((int)(1),x);
    int cnt=pow(x,y/2);
    if(y%2==0)return cnt*cnt;
    else return cnt*cnt*x;
}
inline void read(int &a){
    int x=0,w=1;
    char ch=0;
    while (ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    a=x*w;
}
inline void write(int x) {
    static int sta[35];
    int top=0;
    do{
        sta[top++]=x%10,x/=10;
    }while(x);
    while(top)putchar(sta[--top]+48);
}
#define print(a,n) for(int i=0;i<n;i++){write(a[i]);putchar(' ');}
inline int gcd(int x,int y){
    return (x==0 or y==0)?x+y:gcd(min(x,y),max(x,y)%min(x,y));
}
inline int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
int string_to_int(string s){
    int cur=0;
    for(int i=0;i<s.size();i++)
        cur*=10,cur+=s[i]-'0';
     return cur;
}
string int_to_string(int x){
    string cur;
    while(x){
        cur+=x%10+'0';
        x/=10;
    }
    reverse(cur.begin(),cur.end());
    return cur;
}
inline int divi(int x,int y){return (x+y-1)/y;}
inline bool is_one(int S,int x){return (S>>(x))&1;}
inline int full(int x){return (1<<x)-1;};
inline void swp(int &a,int &b){a^=b,b^=a,a^=b;}
const int N=1e6+5,X=65;//dx[4]={0,0,-1,1};
const int INF=1000000005,mod=1000000007,FINF=-INF;
const ll LINF=1000000000000000005,FLINF=-LINF;
int n,m,c,k,l,r,used[X],use[X];
ll a[N];
vector<int> cnt;
void solve(){
	cin>>n>>m>>c>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++){
		cin>>l>>r;
		use[l]=1;
	}
	for(int j=0;j<k;j++){
		if(!use[j]){
			if(!used[j])cnt.push_back(j);
			used[j]=1;
		}
		for(int i=0;i<n;i++){
			if(use[l] and is_one(a[i],j)==1){
				if(!used[j])cnt.push_back(j);
				used[j]=1;
			}
		}
    }
    cout<<pow(2,cnt.size())-n;
}
signed main(){
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}