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 in 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.

Input

The first line contains four integers $N$, $M$, $Q$ and $K$ $(1\le N,Q,K\le 100000,Q\le N,1\le M\le 200000)$, the number of houses in Birmingham, the number of roads in Birmingham, the number of people that were present in 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

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

Scoring

In the test cases worth a total of $20$ points, it will hold $K=1$, $1\le N,Q\le 100$ and $1\le M\le 200$.

In the test cases worth an additional $15$ points, it will hold $1\le N,Q\le 100$ and $1\le M\le 200$.

Sample Input 1

6 8 1 1
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

Sample Output 1

1 1 2 2 1 0

Sample Input 2

6 8 2 1
6 4
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

Sample Output 2

1 1 1 0 1 0

Sample Input 3

6 8 1 2
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

Sample Output 3

1 1 1 2 1 0

Explanation of Sample Output 3

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.