박람회

어떤 회사가 Byteland에서 박람회를 개최하려고 한다. Byteland에는 n개의 도시와 도시 사이를 잇는 m개의 양방향 도로가 있다. 물론 도로를 이용하면 어느 도시에서든 다른 어느 도시로든 갈 수 있다.

Byteland에서는 k종류의 상품이 생산되며, 각 도시는 오직 한 종류만 생산한다. 박람회를 개최하려면 적어도 s개의 서로 다른 종류의 상품을 가져와야 한다. 도시 u에서 도시 v로 상품을 가져오는 데 d(u,v)개의 동전이 들며, 여기서 d(u,v)는 u에서 v까지의 최단 경로의 길이이다. 경로의 길이는 그 경로에 포함된 도로의 개수이다.

주최 측은 모든 이동 비용을 부담하지만, 상품을 가져올 도시들은 선택할 수 있다. 이제 주최 측은 n개의 각 도시에서 박람회를 개최하기 위한 최소 비용을 계산하려고 한다.

입력의 첫 줄에 4개의 정수 n, m, k, s가 주어진다 (1 ≤ n ≤ $10^{5}$, 0 ≤ m ≤ $10^{5}$, 1 ≤ s ≤ k ≤ min(n, 100)). 각각 도시의 수, 도로의 수, 서로 다른 상품 종류의 수, 박람회 개최에 필요한 서로 다른 상품 종류의 수를 나타낸다.

다음 줄에 n개의 정수 $a_1$, $a_2$, …, $a_n$ (1 ≤ $a_{i}$ ≤ k)가 주어지며, $a_i$는 i-th번째 도시에서 생산되는 상품의 종류이다. 1 이상 k 이하의 모든 정수가 정수들 $a_{i}$ 사이에 적어도 한 번씩 등장함이 보장된다.

다음 m개의 줄에 도로가 설명된다. 각 도로는 두 정수 u v (1 ≤ u, v ≤ n, u ≠ v)로 설명되며, 이 도로가 연결하는 도시들을 나타낸다. 모든 두 도시 사이에는 도로가 최대 하나만 있음이 보장된다. 도로를 통해 어느 도시에서든 다른 어느 도시로든 갈 수 있음이 보장된다.

n개의 수를 출력한다. 그중 i-th번째 수는 도시 i에서 박람회를 개최하기 위해 이동 비용으로 지출해야 하는 최소 동전 개수이다. 수들은 공백으로 구분한다.

첫 번째 예제를 살펴보자's.

도시 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이다.