Điều được biết rằng tất cả các cuộc đua ngựa ở Birmingham đều được sắp xếp trước vài ngày.

Ít người biết rằng, những người sắp xếp những cuộc đua này (và do đó biết người thắng cuộc) thực hiện điều đó tại một cuộc họp bí mật và bắt đầu phổ biến thông tin đó khắp thành phố vào ngày hôm sau.

Ngày đầu tiên sau cuộc họp, tất cả những người biết thông tin về người chiến thắng bắt đầu chia sẻ thông tin đó với tất cả những người sống cách nhà họ không quá ~K~ bước.

Ngày thứ hai sau cuộc họp, tất cả những người biết thông tin về người chiến thắng bắt đầu chia sẻ thông tin đó với tất cả những người sống cách nhà họ không quá ~2 \times K~ bước.

Nói chung, ngày thứ ~X~ sau cuộc họp, tất cả những người biết thông tin về người chiến thắng bắt đầu chia sẻ thông tin đó với tất cả những người sống cách nhà họ không quá ~X \times K~ bước.

Chúng ta có thể mô tả Birmingham dưới dạng một đồ thị nơi các đỉnh đại diện cho các ngôi nhà và các cạnh đại diện cho các con đường hai chiều nối các ngôi nhà này lại. Các ngôi nhà được đánh số tăng dần từ ~1~ đến ~N~ và chúng ta nói rằng một người có thể đi qua mỗi con đường trong một bước. Có thể đi đến mỗi ngôi nhà từ các ngôi nhà khác bằng cách đi qua một chuỗi các con đường.

Nhiệm vụ của bạn là xác định, cho mỗi ngôi nhà, thông tin về người chiến thắng cuộc đua sẽ đến ngôi nhà đó vào ngày nào sau cuộc họp.

Input

• Dòng đầu tiên chứa bốn số nguyên ~N, M, Q~ và ~K~ ~(1 \leq N, Q, K \leq 100 000, Q \leq N, 1 \leq M \leq 200 000)~, số lượng ngôi nhà ở Birmingham, số lượng đường ở Birmingham, số lượng người có mặt tại cuộc họp bí mật và số ~K~ từ mô tả nhiệm vụ.
• Dòng tiếp theo chứa ~Q~ số nguyên trong đó số nguyên thứ ~i~ đại diện cho chỉ số của ngôi nhà nơi người thứ ~i~ từ cuộc họp bí mật sống.
• Mỗi dòng thứ ~i~ trong ~M~ dòng tiếp theo chứa các số nguyên ~A_i~ và ~B_i~ ~(1 \leq A_i, B_i \leq N, A_i \ne B_i)~, chỉ ra rằng con đường thứ ~i~ nối các ngôi nhà có chỉ số ~A_i~ và ~B_i~.

Output

• Xuất ~N~ số trong đó số thứ ~i~ đại diện cho ngày sau cuộc họp mà người sống trong ngôi nhà có chỉ số ~i~ sẽ biết ~a_i~ là người chiến thắng cuộc đua. Nếu người sống trong ngôi nhà đó có mặt tại cuộc họp bí mật, hãy xuất ~0~.

Chú ý

• Trong các trường hợp kiểm tra trị giá tổng cộng 20 điểm, ~K = 1, 1 \leq N, Q \leq 100~ và ~1 \leq M \leq 200~.
• Trong các trường hợp kiểm tra trị giá thêm 15 điểm, ~1 \leq N, Q \leq 100~ và ~1 \leq M \leq 200~.

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 Ouput 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 Ouput 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 Ouput 3

1 1 1 2 1 0

Giải thích

Làm rõ ví dụ thứ ba: Hình ảnh đại diện cho đồ thị từ ví dụ thứ ba. Vì các ngôi nhà 1, 2, 3 và 5 cách ngôi nhà số 6 không quá hai bước, những người sống trong đó sẽ biết về người chiến thắng vào ngày sau cuộc họp. Người sống trong ngôi nhà số 4 sẽ biết về người chiến thắng hai ngày sau cuộc họp.