Migrated from Lutece 3164 零件检查

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

假定某个工厂有 $n$ 间车间，这些车间之间有 $m$ 条路径，保证从任一间车间出发可以到达其他任何一个车间。整个工厂一共生产 $k$ 种零件，其中每个车间只能生产其中一种。 某天领导要对这个工厂的生产的零件进行抽查，抽查的规则如下：

1. 领导莅临其中一间车间 $u$。
2. 通过智能送货小车将车间们生产的零件送至领导处检查，其中从车间 $v$ 送来的零件需要 $dis(u, v)$ 的开销，$dis(u, v)$ 代表的是这两点之间的最短距离。 现在领导要至少检查 $s$ 种零件，作为这个工厂的老板，他希望达成领导的要求同时最小化运输零件的开销，于是命令你这个帕鲁通过编程计算出所有车间满足上述检查条件所需要的最小开销，并输出它们。

Input

第一行输入四个整数 $n,m,k, s$。 第二行输入 $n$ 个整数，每个整数代表车间i生产的零件种类，数据保证每一种零件都至少被一个车间生产。 接下来 $m$ 行每行两个整数 $u,v$ 表示这两个车间之间有一条路径。

Output

输出一行 $n$ 个整数，第 $i$ 个整数代表如果领导在车间 $i$，满足领导检查需求需要的最小开销。

Samples

5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5

2 2 2 2 3

7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7

1 1 1 2 2 1 1

Constraints

$1\le n, m\le 100000$ $1\le k, s \le 100$ 数据保证$s\le k$。

Note

在样例一中： 如果领导位于车间1，选择车间1（0开销）， 2（1开销），4（1开销）此时开销最小为2。其余车间同理。

Resources

2024 UESTC ICPC Training for Graph