D. Ярмарка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Байтландии собираются провести ярмарку. В Байтландии $$$n$$$ городов, которые соединены $$$m$$$ двухсторонними дорогами, причём из любого города можно доехать до любого другого, передвигаясь только по дорогам.

В Байтландии производят $$$k$$$ различных товаров, причём каждый город специализируется на одном товаре. Чтобы ярмарка состоялась, на неё нужно привезти хотя бы $$$s$$$ различных товаров. Чтобы привезти товары из города $$$u$$$ в город $$$v$$$ нужно потратить $$$d(u,v)$$$ монет, где $$$d(u,v)$$$ — длина кратчайшего пути между городами $$$u$$$ и $$$v$$$. Длина пути — это количество дорог, которые входят в этот путь.

Организаторы ярмарки оплатят перевозку товаров, однако они сами могут выбрать, производителей из каких городов пригласить на ярмарку. Теперь организаторы хотят для каждого из $$$n$$$ городов посчитать, какое минимальное количество монет нужно потратить на перевозку товаров, чтобы провести ярмарку в этом городе.

Входные данные

В первой строке записаны $$$4$$$ целых числа $$$n$$$, $$$m$$$, $$$k$$$, $$$s$$$ ($$$1 \le n \le 10^{5}$$$, $$$0 \le m \le 10^{5}$$$, $$$1 \le s \le k \le min(n, 100)$$$) — количество городов, количество дорог, количество различных товаров, количество различных товаров необходимых для проведения ярмарки.

В следующей строке записаны $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_{i} \le k$$$), где $$$a_i$$$ — номер товара, который производится в $$$i$$$-м городе. Гарантируется, что среди чисел $$$a_{i}$$$ встречаются все числа от $$$1$$$ до $$$k$$$.

В следующих $$$m$$$ строках описываются дороги. Каждая дорога описывается парой $$$u$$$ $$$v$$$ городов, которые она соединяет ($$$1 \le u, v \le n$$$, $$$u \ne v$$$). Гарантируется, что между любой парой городов не более одной дороги. Гарантируется, что можно доехать из любого города в любой, двигаясь только по дорогам.

Выходные данные

Выведите $$$n$$$ чисел, $$$i$$$-е из которых — минимальное количество монет на перевозку товаров при проведении ярмарки в городе $$$i$$$. Разделяйте числа пробелами.

Примеры
Входные данные
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
Примечание

Рассмотрим первый пример.

Чтобы провести ярмарку в городе $$$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$$$.