蒟蒻求条80pts#16#17#19#20，hack#2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fr first
#define sd second
#define mkpr make_pair

const int N = 1e6 + 10;

int n, m, k, cnt;
int a[N];
bool is1[65], is2[65];

void write(__int128 t) {
	if (t == 0) return ;
	write(t / 10);
	putchar('0' + t % 10);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
//	freopen("test.txt", "r", stdin);
	cin >> n >> m >> k >> k;
	__int128 l = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		l |= a[i];
	}
	for (int i = 0; i < k; i++)
		if (l & (1 << i))
			is2[i] = 1;
	for (int i = 1; i <= m; i++) {
		int p, q;
		cin >> p >> q;
		is1[p] = 1;
	}
	for (int i = 0; i < k; i++)
		if (!is2[i] && is1[i])
			cnt++;
	__int128 ans = __int128(__int128(1) << (k - cnt)) - n;
	if (ans == 0) cout << 0;
	else write(ans);
	return 0;
}