Some company is going to hold a fair in Byteland. There are $n$ towns in Byteland and $m$ two-way roads between towns. Of course, you can reach any town from any other town using roads.
There are $k$ types of goods produced in Byteland and every town produces only one type. To hold a fair you have to bring at least $s$ different types of goods. It costs $d(u,v)$ coins to bring goods from town $u$ to town $v$ where $d(u,v)$ is the length of the shortest path from $u$ to $v$. Length of a path is the number of roads in this path.
The organizers will cover all travel expenses but they can choose the towns to bring goods from. Now they want to calculate minimum expenses to hold a fair in each of $n$ towns.
## Input
There are $4$ integers $n$, $m$, $k$, $s$ in the first line of input ($1 \le n \le 10^{5}$, $0 \le m \le 10^{5}$, $1 \le s \le k \le min(n, 100)$) — the number of towns, the number of roads, the number of different types of goods, the number of different types of goods necessary to hold a fair.
In the next line there are $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_{i} \le k$), where $a_i$ is the type of goods produced in the $i$\-th town. It is guaranteed that all integers between $1$ and $k$ occur at least once among integers $a_{i}$.
In the next $m$ lines roads are described. Each road is described by two integers $u$ $v$ ($1 \le u, v \le n$, $u \ne v$) — the towns connected by this road. It is guaranteed that there is no more than one road between every two towns. It is guaranteed that you can go from any town to any other town via roads.
## Output
Print $n$ numbers, the $i$\-th of them is the minimum number of coins you need to spend on travel expenses to hold a fair in town $i$. Separate numbers with spaces.
[samples]
## Note
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$.
某公司将在Byteland举办一场集市。Byteland中有$n$座城镇和$m$条双向道路。当然，通过道路可以从任意城镇到达其他任意城镇。
Byteland生产$k$种商品，每座城镇只生产一种商品。要举办一场集市，你需要至少带来$s$种不同类型的商品。从城镇$u$将商品运送到城镇$v$需要花费$d(u, v)$枚硬币，其中$d(u, v)$是$u$到$v$的最短路径长度（路径长度定义为路径中的道路数量）。
组织者将承担所有运输费用，但他们可以选择从哪些城镇运送商品。现在他们希望计算在每座城镇举办集市所需的最小费用。
输入第一行包含$4$个整数$n$，$m$，$k$，$s$（$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$，$1 \leq s \leq k \leq \min(n, 100)$）——分别表示城镇数量、道路数量、不同商品类型数量以及举办集市所需的最少商品类型数量。
接下来一行包含$n$个整数$a_1, a_2, \dots, a_n$（$1 \leq a_i \leq k$），其中$a_i$表示第$i$座城镇生产的商品类型。保证$1$到$k$之间的每个整数在$a_i$中至少出现一次。
接下来$m$行描述道路。每条道路由两个整数$u$ $v$（$1 \leq u, v \leq n$，$u \neq v$）描述，表示这两座城镇之间有一条道路。保证任意两座城镇之间最多只有一条道路，且任意两座城镇均可通过道路相互到达。
请输出$n$个数，第$i$个数表示在第$i$座城镇举办集市所需的最小运输费用。数字之间用空格分隔。
让我们看第一个样例。
要在城镇$1$举办集市，你可以从城镇$1$（花费$0$枚硬币）、城镇$2$（花费$1$枚硬币）和城镇$4$（花费$1$枚硬币）运送商品。总花费为$2$枚硬币。
城镇$2$：从城镇$2$（$0$）、城镇$1$（$1$）、城镇$3$（$1$）运送商品。总和为$2$。
城镇$3$：从城镇$3$（$0$）、城镇$2$（$1$）、城镇$4$（$1$）运送商品。总和为$2$。
城镇$4$：从城镇$4$（$0$）、城镇$1$（$1$）、城镇$5$（$1$）运送商品。总和为$2$。
城镇$5$：从城镇$5$（$0$）、城镇$4$（$1$）、城镇$3$（$2$）运送商品。总和为$3$。
## Input
输入第一行包含$4$个整数$n$，$m$，$k$，$s$（$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$，$1 \leq s \leq k \leq \min(n, 100)$）——分别表示城镇数量、道路数量、不同商品类型数量以及举办集市所需的最少商品类型数量。接下来一行包含$n$个整数$a_1, a_2, \dots, a_n$（$1 \leq a_i \leq k$），其中$a_i$表示第$i$座城镇生产的商品类型。保证$1$到$k$之间的每个整数在$a_i$中至少出现一次。接下来$m$行描述道路。每条道路由两个整数$u$ $v$（$1 \leq u, v \leq n$，$u \neq v$）描述，表示这两座城镇之间有一条道路。保证任意两座城镇之间最多只有一条道路，且任意两座城镇均可通过道路相互到达。
## Output
请输出$n$个数，第$i$个数表示在第$i$座城镇举办集市所需的最小运输费用。数字之间用空格分隔。
[samples]
## Note
让我们看第一个样例。
要在城镇$1$举办集市，你可以从城镇$1$（花费$0$枚硬币）、城镇$2$（花费$1$枚硬币）和城镇$4$（花费$1$枚硬币）运送商品。总花费为$2$枚硬币。
城镇$2$：从城镇$2$（$0$）、城镇$1$（$1$）、城镇$3$（$1$）运送商品。总和为$2$。
城镇$3$：从城镇$3$（$0$）、城镇$2$（$1$）、城镇$4$（$1$）运送商品。总和为$2$。
城镇$4$：从城镇$4$（$0$）、城镇$1$（$1$）、城镇$5$（$1$）运送商品。总和为$2$。
城镇$5$：从城镇$5$（$0$）、城镇$4$（$1$）、城镇$3$（$2$）运送商品。总和为$3$。
Let $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = n $, $ |E| = m $.
Let $ a: V \to \{1, 2, \dots, k\} $ be a function assigning to each town $ v \in V $ a good type $ a_v $.
Let $ d(u, v) $ denote the shortest path distance (number of edges) between nodes $ u $ and $ v $ in $ G $.
Let $ s \in \mathbb{N} $, $ 1 \le s \le k \le \min(n, 100) $.
For each town $ i \in V $, define the cost $ C(i) $ as the minimum total distance required to collect at least $ s $ distinct good types, where goods may be sourced from any town $ j \in V $, and the cost of sourcing from $ j $ is $ d(i, j) $.
Formally, for each $ i \in V $:
$$
C(i) = \min_{\substack{S \subseteq V \\ |\{a_j \mid j \in S\}| \ge s}} \sum_{j \in S} d(i, j)
$$
Equivalently, for each town $ i $, consider the multiset of distances from $ i $ to all towns, grouped by good type. For each good type $ t \in \{1, \dots, k\} $, let $ D_i(t) = \min \{ d(i, j) \mid a_j = t \} $ be the minimum distance from $ i $ to any town producing type $ t $. Then:
$$
C(i) = \sum_{t \in T_i} D_i(t)
$$
where $ T_i \subseteq \{1, \dots, k\} $ is a subset of $ s $ good types minimizing $ \sum_{t \in T_i} D_i(t) $, i.e., the $ s $ smallest values among $ \{ D_i(1), D_i(2), \dots, D_i(k) \} $.
Thus, the solution for each town $ i $ is the sum of the $ s $ smallest values in the vector $ \left( D_i(1), D_i(2), \dots, D_i(k) \right) $.
**Algorithmic summary:**
- For each good type $ t \in \{1, \dots, k\} $, perform a BFS from all nodes $ j $ with $ a_j = t $ simultaneously (multi-source BFS) to compute $ D_i(t) = \min \{ d(i, j) \mid a_j = t \} $ for all $ i \in V $.
- For each town $ i $, collect $ D_i(1), \dots, D_i(k) $, sort them, and take the sum of the smallest $ s $ values.
**Output:** $ C(1), C(2), \dots, C(n) $