Ở thành phố Birmingham, mọi người rất quan tâm đến các cuộc đua ngựa. Tuy nhiên ít ai biết rằng người chiến thắng các cuộc đua được quyết định trong những cuộc họp kín trước cả khi cuộc đua thực sự diễn ra. Những người dự họp sau khi tan họp về nhà sẽ bắt đầu truyền thông tin ra khắp thành phố.

Ngày đầu tiên sau cuộc họp, những người sống cách không quá ~K~ (~K~ là hệ số cho trước) bước từ nhà của một người đã biết tin sẽ biết được người chiến thắng đã được quyết định. Ngày thứ hai sau cuộc họp, những người sống cách nhà của một người đã biết tin không quá ~2 \cdot K~ bước sẽ biết được người chiến thắng. Tổng quát hơn, ~X~ ngày sau cuộc họp thì những người sống cách không quá ~X \cdot K~ bước từ một người đã biết tin sẽ biết được người chiến thắng.

Thành phố Birmingham được biểu diễn dưới dạng đồ thị vô hướng. Mỗi nhà được đánh số từ ~1~ đến ~N~ và hai nhà liền kề được nối bởi một con đường. Có thể qua lại những nhà không kề nhau thông qua một hay nhiều con đường.

Với mỗi nhà, xác định chủ nhà sẽ biết được người chiến thắng sớm nhất khi nào.

Input

• Dòng đầu tiên chứa 4 số nguyên dương ~N~, ~M~, ~Q~, ~K~ (~N, Q, K \leq 10^5~, ~M \leq 2 \cdot 10^5~) là số căn nhà trong thành phố, số con đường, số người đã dự họp và hệ số ~K~ trong đề bài.
• Dòng tiếp theo chứa ~Q~ số nguyên dương cho biết những căn nhà có người dự họp.
• Mỗi dòng trong ~M~ dòng tiếp theo chứa 2 số nguyên dương ~A~, ~B~ cho biết có đường nối trực tiếp giữa 2 căn nhà ~A~ và ~B~.

Output

Với mỗi căn nhà ở Birmingham, cho biết ngày sớm nhất mà chủ nhà biết tin. Quy ước rằng nếu chủ nhà dự họp thì ngày biết tin là ngày ~0~.

Ví dụ

Sample input 1

6 8 1 1
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

Sample output 1

1 1 2 2 1 0

Sample input 2

6 8 2 1
6 4
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

Sample output 2

1 1 1 0 1 0

Sample input 3

6 8 1 2
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

Sample output 3

1 1 1 2 1 0

Ghi chú

Giải thích cho ví dụ 3: Vì nhà ~1~, ~2~, ~3~ và ~5~ đều cách nhà ~6~ không quá ~2~ bước nên chủ những nhà ấy sẽ biết tin ~1~ ngày sau ngày họp. Chủ nhà ~4~ sẽ biết tin sau ~2~ ngày.