Zoo Feed List Extension Counting

The zoo breeds many animals. There are \(2^k\) different kinds of animals numbered from \(0\) to \(2^k-1\), each represented as a \(k\)-bit binary string (with the \(0\)th bit as the least significant bit). The zoo currently houses \(n\) species with numbers \(a_0, a_1, \dots, a_{n-1}\).

The Feeding Guidelines contain \(m\) requirements. The \(j\)th requirement is as follows: "If the zoo breeds an animal whose binary representation has the \(p_j\)th bit equal to 1, then feed type \(q_j\) must be purchased." There are \(c\) types of feed, numbered from \(1\) to \(c\). Based on these rules, caretaker A prepares a feed list for procurement. The feed list is a \(c\)-character string composed of 0s and 1s, where the \(i\)th bit is 1 if feed type \(i\) is required and 0 otherwise.

In fact, after the feed is purchased, it is possible that the zoo can support more animal species. More specifically, if an animal with number \(x\) (which is not currently present) is added to the zoo and the feed list remains unchanged, then we say the zoo is capable of supporting animal \(x\) as well.

Your task is to calculate how many additional animal species (i.e. numbers \(x\) not already present in \(\{a_0,a_1,\dots,a_{n-1}\}\)) can be added such that the feed list does not change.

How to Determine the Valid Extensions

First, the feed list based on the current animals is determined as follows. For each requirement \(j\) (\(1 \le j \le m\)), if there exists an animal \(a\) among the current ones with its \(p_j\)th bit equal to 1, then feed type \(q_j\) is set to 1 in the list. For every requirement \(j\) for which feed type \(q_j\) is 0 in the feed list (i.e. no current animal has its \(p_j\)th bit as 1), any new animal \(x\) must also have a 0 at the \(p_j\)th bit; otherwise the feed list would change.

Let \(S\) be the set of bit positions that are forced to 0 (i.e. for every requirement \(j\) with feed \(q_j = 0\), bit \(p_j\) must be 0 in any additional animal). If we let \(\text{free}\) be the number of bits that are not forced (i.e. \(\text{free} = k - |S|\)), then the total number of animal numbers in \([0,2^k-1]\) satisfying the forced conditions is \(2^{\text{free}}\).

Since the current animals are already in the zoo, the final answer is:

[ \text{answer} = 2^{\text{free}} - \big|{a_i \mid 0 \le i < n \text{ and } (a_i \mathbin{&} M)=0}\big|, ]

where \(M\) is a bitmask with 1s at the forced bit positions.

inputFormat

The first line contains four integers \(k, n, m, c\).

The second line contains \(n\) integers \(a_0, a_1, \dots, a_{n-1}\) representing the animal numbers currently in the zoo.

The following \(m\) lines each contain two integers \(p_j\) and \(q_j\) representing a requirement.

outputFormat

Output a single integer representing the number of additional animal species that can be added without changing the feed list.

sample

3 2 2 3
1 4
0 2
2 3

6