题目描述

众所周知，伯明翰的所有赛马比赛都是提前几天进行的。 修复这些比赛的人（因此知道 获胜者）在秘密会议上这样做并开始传播信息 在那次会议之后的第二天，在城市周围。

会议结束后的第一天，所有知道有关信息的人 获胜者开始与所有最多生活的人分享这些信息 K 离他们家几步远。

会议后的第二天，所有知道获胜者信息的人开始分享 与所有居住在离他们家最多 2·K 步的人有关的信息。

一般来说，会议结束后的第 X 天，所有知道获胜者信息的人都会开始 与所有居住在离他们家最多 X·K 步的人分享这些信息。

我们可以将伯明翰表示为一个图，其中顶点表示房屋，边表示 连接这些房屋的双向道路。房屋用从 1 到 N 递增的整数进行索引 我们说一个人可以一步走完每条路。可以从 穿过一系列的道路，彼此房屋。

你的任务是确定，对于每个房子，关于比赛获胜者的信息将在哪一天到达 它。

输入格式

第一行包含四个整数 N、M、Q 和 K（1 ≤ N、Q、K ≤ 100 000、Q ≤ N、1 ≤ M ≤ 200 000）， 伯明翰的房屋数量，伯明翰的道路数量， 出席了秘密会议和任务描述中的数字 K。

下一行包含 Q 个整数，其中第 i 个整数表示第 i 个房子的索引 秘密会议的人住在里面。

接下来 M 行的第 i 行包含整数 Ai 和 Bi (1 ≤ Ai , Bi ≤ N, Ai 6 = Bi), 表示 第 i 条道路用索引 Ai 和 Bi 连接房屋。

输出格式

输出 N 个数字，其中第 i 个数字代表会议后的哪一天 住在有索引的房子里，我知道谁会赢得比赛。 如果住在那个房子里的人在场 在秘密会议上，改为输出 0。

样例 #1

样例输入 #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

样例输入 #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

样例输入 #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

提示

样例 #3 解释

该图表示来自第三个示例的图表。 自从 1、2、3、5号房离6号房最多只有两步，住在里面的人会发现 会议后第二天获胜。 住在 4 号房子的人将在两天内了解获胜者的信息 会后。

数据规模及约定

在总分 20 分的测试用例中，它将保持 K = 1、1 ≤ N、Q ≤ 100 和 1 ≤ M ≤ 200。

在额外 15 分的测试用例中，它将保持 1 ≤ N、Q ≤ 100 和 1 ≤ M ≤ 200。