众所周知，伯明翰的所有赛马比赛都是提前几天安排好的。不太为人所知的是，操纵这些比赛（从而得知获胜者）的人是在一次秘密会议上进行的，并在会议结束后的第二天开始在城市里传播这个消息。

在会议结束后的第一天，所有知道获胜者信息的人开始与距离自己家最多 $K$ 步的所有人分享该信息。

在会议结束后的第二天，所有知道获胜者信息的人开始与距离自己家最多 $2 \cdot K$ 步的所有人分享该信息。

一般来说，在会议结束后的第 $X$ 天，所有知道获胜者信息的人开始与距离自己家最多 $X \cdot K$ 步的所有人分享该信息。

我们可以将伯明翰表示为一个图，其中顶点表示房屋，边表示连接这些房屋的双向道路。房屋用从 $1$ 到 $N$ 的递增整数进行编号，我们称一个人可以在单步内通过每条道路。可以通过穿过一系列道路从任何一栋房屋到达任何其他房屋。

你的任务是确定对于每栋房屋，关于赛马获胜者的信息将在哪一天传到它。

输入格式

第一行包含四个整数 $N, M, Q$ 和 $K$ ($1 \le N, Q, K \le 100\,000, Q \le N, 1 \le M \le 200\,000$)，分别表示伯明翰的房屋数量、道路数量、参加秘密会议的人数以及题目描述中的数量 $K$。

第二行包含 $Q$ 个整数，其中第 $i$ 个整数表示参加秘密会议的第 $i$ 个人所居住的房屋编号。

接下来的 $M$ 行中，第 $i$ 行包含整数 $A_i$ 和 $B_i$ ($1 \le A_i, B_i \le N, A_i \neq B_i$)，表示第 $i$ 条道路连接编号为 $A_i$ 和 $B_i$ 的房屋。

输出格式

输出 $N$ 个数字，其中第 $i$ 个数字表示在会议结束后的第几天，住在编号为 $i$ 的房屋中的人会得知谁将赢得比赛。如果住在该房屋中的人参加了秘密会议，则输出 $0$。

子任务

在占总分 20 分的测试数据中，满足 $K = 1, 1 \le N, Q \le 100$ 且 $1 \le M \le 200$。

在另外占总分 15 分的测试数据中，满足 $1 \le N, Q \le 100$ 且 $1 \le M \le 200$。

样例

输入样例 1

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

输出样例 1

1 1 2 2 1 0

输入样例 2

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

输出样例 2

1 1 1 0 1 0

输入样例 3

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

输出样例 3

1 1 1 2 1 0

说明

第三个样例的解释：下图表示第三个样例中的图。由于房屋 1, 2, 3 和 5 距离房屋 6 最多两步，住在这些房屋里的人将在会议结束后的第一天得知获胜者。住在房屋 4 的人将在会议结束后的第二天得知获胜者。