CF986A Fair

一些公司将在Byteland举办商品交易会（or博览会？）。在Byteland有 $n$ 个城市，城市间有 $m$ 条双向道路。当然，城镇之间两两连通。 Byteland生产的货物有 $k$ 种类型，每个城镇只生产一种。 为了举办商品交易会，你必须至少带来 $s$ 种不同类型的商品。将货物从 $u$ 镇带到城镇 $v$ 将花费 $d(u,v)$ 的费用，其中 $d(u,v)$ 是从 $u$ 到 $v$ 的最短路径的长度。 路径的长度是这个路径中的道路的数量。 组织者将支付所有的运输费用，但他们可以选择从哪些城镇带来货物。现在他们想计算每个城镇举办商品交易会的最小费用。

第一行 $4$ 个整数$n$ , $m$ , $k$ , $s$ ($1\le n\le 10^5 $,$1\le m\le 10^5 $,$1\le s\le k\le min(n,100)$ )——分别表示 城镇数，道路数，生产的货物数，举办商品交易会所需的货物数。 接下来一行$n$个整数$a_1,a_2,...,a_n(1\le a_i \le k)$ , $a_i$是第$i$个城镇生产的商品种类.保证$1$和$k$之间的所有整数在整数$a_i$中至少出现一次。 接下来$m$行表示道路。每行两个整数 $u$ $v$ $(1 \le u$,$v \le n, u\ne v)$ 表示 $u$ $v$ 之间有一条双向道路。保证每两个城镇之间只有一条路。并且城镇之间两两连通。

输出$n$个数。第$i$个数表示在第$i$个城镇举办商品交易会所需花在运输上的最小费用。数与数之间用空格分开。

Let's look at the first sample. To hold a fair in town $ 1 $ you can bring goods from towns $ 1 $ ( $ 0 $ coins), $ 2 $ ( $ 1 $ coin) and $ 4 $ ( $ 1 $ coin). Total numbers of coins is $ 2 $ . Town $ 2 $ : Goods from towns $ 2 $ ( $ 0 $ ), $ 1 $ ( $ 1 $ ), $ 3 $ ( $ 1 $ ). Sum equals $ 2 $ . Town $ 3 $ : Goods from towns $ 3 $ ( $ 0 $ ), $ 2 $ ( $ 1 $ ), $ 4 $ ( $ 1 $ ). Sum equals $ 2 $ . Town $ 4 $ : Goods from towns $ 4 $ ( $ 0 $ ), $ 1 $ ( $ 1 $ ), $ 5 $ ( $ 1 $ ). Sum equals $ 2 $ . Town $ 5 $ : Goods from towns $ 5 $ ( $ 0 $ ), $ 4 $ ( $ 1 $ ), $ 3 $ ( $ 2 $ ). Sum equals $ 3 $ .