It is well known that all horse races in Birmingham are fixed days in advance. It is a little less known that people who fix these races (and thereby know the winner) do that on a secret meeting and start spreading the information around the city the day after that meeting. The first day after the meeting, all people that know the information about the winner start sharing that information with all people that live at most $K$ steps away from their house. The second day after the meeting, all people that know the information about the winner start sharing that information with all people that live at most $2 \cdot K$ steps away from their house. In general, $X$-th day after the meeting, all people that know the information about the winner start sharing that information with all people that live at most $X \cdot K$ steps away from their house. We can represent Birmingham as a graph where vertices represent the houses and edges represent bidirectional roads which connect these houses. Houses are indexed with increasing integers from $1$ to $N$ and we say that a person can travel each road in a single step. It is possible to reach each house from each other house by traversing a sequence of roads. Your task is to determine, for each house, on which day will the information about the race winner reach it.

The first line contains four integers $N$, $M$, $Q$ and $K$ $(1 \le N, Q, K \le 100\,000,\ Q \le N,\ 1 \le M \le 200\,000)$, the number of houses in Birmingham, the number of roads in Birmingham, the number of people that were present on the secret meeting and the number $K$ from task description. The next line contains $Q$ integers where the $i$-th integer represents the index of a house where the $i$-th person from the secret meeting lives in. The $i$-th of the next $M$ lines contains integers $A_i$ and $B_i$ $(1 \le A_i, B_i \le N,\ A_i \ne B_i)$, which denote that the $i$-th road connects houses with indices $A_i$ and $B_i$.

Output $N$ numbers where the $i$-th number represents on which day after the meeting will the person living in house with index $i$ find out who will win the race. If the person living in that house was present on the secret meeting, output `0` instead.

**Clarification of the third example:** The figure represents a graph from the third example. Since houses $1$, $2$, $3$ and $5$ are at most two steps away from house $6$, people living in them will find out about the winner the day after the meeting. Person living in house $4$ will find out about the winner two days after the meeting. <div class='text-center'><img src='/userfiles/images/72ee1e0d-a21b-48a0-b559-7b43b75dde0b.png'/></div>

COCI 2019/2020 CONTEST #6