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 \times 10^5, 0 ≤ d ≤ 365)~. People are numbered from ~0~ to ~n – 1~.
• The ~i^{th}~ number in the second line represents the date of birth of the ~i^{th}~ 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 Input

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

Sample Output

2
2
1
1
1