Person in Charge

Problem Description

A zoo keeps a large number of animals. The zookeeper A will purchase different types of feed according to the animal breeding situation in accordance with the Feeding Guide, and send the purchase list to the purchaser B.

Specifically, there are $2^k$ different types of animals in the animal kingdom, numbered from $0$ to $2^k - 1$. The zoo keeps $n$ of these types, where the number of the $i$-th type of animal is $a_i$.

The Feeding Guide contains $m$ requirements. The $j$-th requirement is in the form of "If the zoo keeps an animal whose binary representation of the number has the $p_j$-th bit as $1$, then the $q_j$-th type of feed must be purchased". There are a total of $c$ types of feed, numbered from $1$ to $c$. In this problem, we regard the binary representation of an animal's number as a $k$-bit 01 string, where the $0$-th bit is the least significant bit and the $k - 1$-th bit is the most significant bit.

According to the Feeding Guide, zookeeper A will make a feed list and hand it over to purchaser B, who will then buy the feed. The list is in the form of a $c$-bit 01 string: the $i$-th bit being $1$ means the $i$-th type of feed needs to be purchased, and $0$ means it does not. In fact, based on the purchased feed, the zoo may be able to keep more animals. More specifically, if adding an unpurchased animal with number $x$ to the zoo's breeding list does not change the feed list, then we consider that the zoo can currently keep the animal with number $x$.

Now purchaser B wants you to help calculate how many more types of animals the zoo can currently keep.

Input Format

The first line contains four integers $n, m, c, k$ separated by spaces, representing the number of animals in the zoo, the number of requirements in the Feeding Guide, the number of feed types, and the number of bits in the binary representation of animal numbers, respectively.
The second line contains $n$ integers separated by spaces, where the $i$-th integer is $a_i$.
The next $m$ lines each contain two integers $p_i, q_i$ representing a requirement.

It is guaranteed that all $a_i$ are distinct and all $q_i$ are distinct.

Output Format

Output a single integer on one line representing the answer.

Samples

3 3 5 4
1 4 6
0 3
2 4
2 5

13

Sample 1 Explanation

The zoo keeps three animals numbered $1, 4, 6$. The three requirements in the Feeding Guide are:

1. If the zoo keeps an animal whose number has the $0$-th binary bit as $1$, then the $3$-rd type of feed must be purchased.
2. If the zoo keeps an animal whose number has the $2$-nd binary bit as $1$, then the $4$-th type of feed must be purchased.
3. If the zoo keeps an animal whose number has the $2$-nd binary bit as $1$, then the $5$-th type of feed must be purchased.

The feed purchase status is as follows:

1. The $0$-th binary bit of the number of the animal numbered $1$ is $1$, so the $3$-rd type of feed needs to be purchased;
2. The $2$-nd binary bit of the numbers of the animals numbered $4$ and $6$ is $1$, so the $4$-th and $5$-th types of feed need to be purchased.

Since adding an animal numbered $0, 2, 3, 5, 7, 8, \ldots, 15$ to the current zoo will not change the shopping list, the answer is $13$.

Sample 2

See zoo/zoo2.in and zoo/zoo2.ans in the contestant's directory.

Sample 3

See zoo/zoo3.in and zoo/zoo3.ans in the contestant's directory.

Data Range

For $20\%$ of the data: $k \le n \le 5$, $m \le 10$, $c \le 10$, and all $p_i$ are distinct.
For $40\%$ of the data: $n \le 15$, $k \le 20$, $m \le 20$, $c \le 20$.
For $60\%$ of the data: $n \le 30$, $k \le 30$, $m \le 1000$.
For $100\%$ of the data: $0 \le n, m \le 10^6$, $0 \le k \le 64$, $1 \le c \le 10^8$.