EIU Programming Practices and Exams

Today Ngan and her friends want to go buy gifts for their birthday friends next week. Given friend relationships, each person's birthday and current date. For each person, tell us how many of your friends have birthdays within the next k days (including the current date). Assume that the years considered are not leap years.

Input

The first line contains 4 integers: n, m, d, k are the number of people, the number of friendships, the current date. (0 ≤ n, m ≤ 2 * 10⁵_, 0 ≤ d ≤ 365). People are numbered from 0 to n – 1.

The ith number in the second line represents the date of birth of the ith person (day of year). (0 ≤ b_i ≤ 365).

Each of the following m lines contains two integers u, v denoting that u and v are friends.

Output

For each person, output the number of friends that have birthdays in the next k days in one line.

Sample