Nhiều công ty muốn tổ chức hội chợ ở vùng đất Byteland xinh đẹp. Vùng đất này có ~ n ~ thị trấn có số hiệu từ 1 đến ~ n ~ và ~ m ~ con đường nối liền ~ n ~ thị trấn, giữa hai thị trấn bất kỳ có tối đa 1 con đường hai chiều. Có ~ k ~ loại hàng hóa được sản xuất ở Byteland tuy nhiên mỗi thị trấn chỉ sản xuất một loại hàng hóa duy nhất. Để tổ chức hội chợ cần có ít nhất ~ s ~ loại hàng hóa được đưa đến 1 thị trấn bất kỳ. Chi phí để vận chuyển một loại hàng hóa từ thị trấn ~ u ~ đến thị trấn ~ v ~ là ~ d(u,v) ~ chính là độ dài được đi ngắn nhất từ thị trấn ~ u ~ đến thị trấn ~ v ~. Độ dài của một đường đi là số lượng con đường trên đường đi đó. Hãy cho biết muốn tổ chức hội chợ ở một thị trấn ~ u ~ bất kỳ thì chi phí tối thiểu để vận chuyển ít nhất ~ s ~ loại hàng hóa khác nhau đến thị trấn ~ u ~ là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên chứa 4 số nguyên dương ~ n, m, k, s ~ lần lượt là số lượng thị trấn, số lượng con đường 2 chiều, số loại hoàng hóa khác nhau và số lượng hàng hóa khác nhau cần thiết để tổ chức hội chợ.
• Dòng tiếp theo ghi ~ n ~ số nguyên dương ~ a_1, a_2,…,a_n (1 ≤ a_i ≤ k) ~ trong đó ai là loại hàng hóa mà thị trấn thứ ~ i ~ sản xuất.
• Tiếp theo là ~ m ~ dòng, mỗi dòng gồm 2 số nguyên dương ~ u ~ và ~ v ~ cho biết có 1 đường trực tiếp nối thị trấn ~u ~ và thị trấn ~ v ~.

Kết quả

Gồm ~ n ~ số nguyên trong đó số thứ ~ i ~ cho biết chi phí tối thiểu vận chuyển các loại hàng hóa để có thể tổ chức hội chợ ở thị trấn thứ ~ i ~.

Ràng buộc

• ~ 1 ≤ n ≤ 10^5 ~
• ~ 0 ≤ m ≤ 10^5 ~
• ~ 1 ≤ s ≤ k ≤ min(n,100) ~

Ví dụ:

Input 1

5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5 

Output 1

2 2 2 2 3 

Input 2

7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7 

Output 2

1 1 1 2 2 1 1