EIU Programming Practices and Exams

Today, Phuc and his friends go shopping to buy gifts for their friends who have birthday on next few days. Given the list of friendships and the birthday of each person and current date, calcute the number of gifts each person need to buy for their friends who have birthday in the next k days (including today). We can assume that every mentioned year is not leap year.

Input

The first line contains 4 integers: n, m, d, k, respectively, number of people, number of friend relationships, current date. (0 ≤ n, m ≤ 2 * 10⁵_, 0 ≤ d ≤ 365 ). Each person is numbered from 0 to n - 1

The i^th integer in the following line represents the birthday of the i ^th person(ngày trong năm) (0 ≤ b_i ≤ 365).

In the next m lines, each line contains two integers u, v indicating that u and v are friends.

Output

For each person, in order from 0 to n-1, output the number of friends who have birthday for the next k days on one line.

Example

Input:

5 6 10 7
9 10 15 16 18
1 3
1 4
1 2
0 2
4 0
0 1

Output:
2 2 1 1 1