Một số thành viên của câu lạc bộ "Vì cuộc sống xanh" ở thành phố XYZ đang tham dự hội nghị thảo luận về một số biện pháp hạn chế rác thải nhựa. Sau hội nghị, các thành viên này quyết định sẽ thông tin nội dung hội nghị đến từng thành viên trong câu lạc bộ theo cách sau:

• Ngày đầu tiên sau hội nghị, tất cả các thành viên dự hội nghị sẽ truyền tin cho những người sống cách nhà của họ không quá ~K~ giờ di chuyển.
• Ngày thứ hai sau hội nghị, tất cả những người nhận được thông tin sẽ truyền tin cho những người sống cách nhà của họ không quá ~2 \times K~ giờ di chuyển.
• Ngày thứ ~X~ sau hội nghị, tất cả những người biết thông tin về nội dung hội nghị sẽ truyền tin cho những người sống cách nhà của họ không quá ~X \times K~ giờ di chuyển. Nhà của các thành viên trong câu lạc bộ được đánh số từ ~1~ đến ~N~. Giữa hai nhà có nhiều nhất một con đường hai chiều để đi qua lại và mất một giờ để di chuyển từ nhà ở đầu này đến nhà ở đầu kia con đường. Từ một nhà bất kì có thể đến nhà khác bằng cách đi theo các con đường nối giữa hai nhà.

Yêu cầu:

Cho bản đồ thành phố XYZ, hãy lập trình cho biết thời gian nhận được thông tin của từng thành viên trong câu lạc bộ "Vì cuộc sống xanh".

Dữ liệu vào:

• Dòng thứ nhất chứa ~4~ số nguyên: ~N~ (số người trong câu lạc bộ), ~M~ (số con đường), ~Q~ (số người tham dự hội nghị), ~K~(số giờ di chuyển), với ~1 ≤ N, Q, K ≤ 100 000, Q ≤ N, 1≤ M ≤ 200000~;
• Dòng thứ hai chứa ~Q~ số nguyên, mỗi số là số nhà của những người tham gia hội nghị;
• ~M~ dòng tiếp theo, mỗi dòng ghi ~2~ số nguyên dương ~u~ và ~v~ cho biết thông tin: Giữa hai nhà ~u~ và ~v~ có một đường đi trực tiếp. Các số trên cùng một dòng cách nhau ít nhất một dấu cách.

Kết quả ra:

Gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (mỗi số cách nhau ít nhất một dấu cách), số thứ ~i~ cho biết sau hội nghị ~A_i~ ngày thì người sống trong nhà thứ ~i~ nhận được thông tin về nội dung hội nghị. Nếu người sống trong nhà thứ ~i~ tham gia hội nghị thì ~A_i = 0~.

Sample Input

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 2 2 1 0