There are $2^k$ different types of animals in the animal world, numbered from $0$ to $2^k - 1$. The zoo currently keeps $n$ of these types, where the $i$-th type of animal has the ID $a_i$.

There are $m$ requirements in the "Feeding Guide". The $j$-th requirement is of the form: "If an animal is kept in the zoo such that the $p_j$-th bit of its ID in binary representation is $1$, then the $q_j$-th type of feed must be purchased." There are $c$ types of feed in total, numbered from $1$ to $c$. In this problem, we treat the binary representation of an animal's ID as a $k$-bit 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", keeper A will create a feed list for purchaser B. The list is a $c$-bit string where the $i$-th bit being $1$ means the $i$-th type of feed must be purchased, and the $i$-th bit being $0$ means it does not need to be purchased.

In reality, based on the feed purchased, the zoo might be able to keep more animals. Specifically, if adding an animal with ID $x$ (which is not currently kept) to the zoo does not change the feed list, then we consider that the zoo can currently keep an animal with ID $x$.

Now, B would like you to help calculate how many more types of animals the zoo can currently keep.

Input

The first line contains four space-separated integers $n, m, c, k$. These represent 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 IDs, respectively.

The second line contains $n$ space-separated integers, where the $i$-th integer represents $a_i$.

The next $m$ lines each contain two integers $p_j, q_j$, representing a requirement.

It is guaranteed that all $a_i$ are distinct, and all $q_j$ are distinct.

Output

A single integer representing the answer.

Examples

Input 1

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

Output 1

13

Note 1

The zoo keeps three types of animals with IDs $1, 4, 6$. The 3 requirements in the "Feeding Guide" are: 1. If the $0$-th binary bit of the ID of a kept animal is $1$, then the $3$-rd type of feed must be purchased. 2. If the $2$-nd binary bit of the ID of a kept animal is $1$, then the $4$-th type of feed must be purchased. 3. If the $2$-nd binary bit of the ID of a kept animal is $1$, then the $5$-th type of feed must be purchased.

The feed purchase situation is: 1. The $0$-th binary bit of the animal with ID $1$ is $1$, so the $3$-rd type of feed must be purchased. 2. The $2$-nd binary bit of the animals with IDs $4$ and $6$ is $1$, so the $4$-th and $5$-th types of feed must be purchased.

Since adding an animal with any ID from $0, 2, 3, 5, 7, 8, \dots, 15$ to the current zoo does not change the shopping list, the answer is $13$.

Input 2

2 2 4 3
1 2
1 3
2 4

Output 2

2

Examples 3

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

Constraints

• For $20\%$ of the data: $k \le 5, m \le 10, c \le 10$, 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$.