Hội chợ

Đất nước Byteland có $n$ thành phố và $m$ con đường hai chiều, đảm bảo có thể đi từ thành phố bất kỳ tới thành phố bất kỳ khác bằng các con đường.

Byteland sản xuất $k$ loại hàng hoá, mỗi thành phố chỉ sản xuất đúng một loại. Để tổ chức một hội chợ tại thành phố $v$, ban tổ chức phải mang về đó ít nhất $s$ loại hàng hoá khác nhau. Chi phí vận chuyển hàng hoá từ thành phố $u$ về thành phố $v$ bằng $d(u,v)$ đồng, trong đó $d(u,v)$ là số con đường trên đường đi ngắn nhất giữa $u$ và $v$.

Ban tổ chức được tự do chọn lấy hàng từ thành phố nào (miễn là gom đủ $s$ loại khác nhau). Với mỗi thành phố, hãy tính chi phí vận chuyển nhỏ nhất để tổ chức hội chợ tại đó.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n$, $m$, $k$, $s$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, trong đó $a_i$ là loại hàng hoá thành phố $i$ sản xuất.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$, $v$ mô tả một con đường nối thành phố $u$ và thành phố $v$.

Dữ liệu ra

In ra $n$ số cách nhau bởi dấu cách, số thứ $i$ là chi phí vận chuyển nhỏ nhất để tổ chức hội chợ tại thành phố $i$.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le m\le {10}^5$
• $1\le s\le k\le min(n,100)$
• $1\le a_i\le k$, và mỗi giá trị từ $1$ tới $k$ đều xuất hiện ít nhất một lần trong dãy $a$
• $1\le u,v\le n$, $u\ne v$; giữa hai thành phố bất kỳ có nhiều nhất một con đường

Ví dụ