Vào cuộc họp kín trong buổi tiệc Thank you party vừa qua, chủ nhiệm Rec là lãnh đạo của tổ chức áo đen tại IUH đã tiết lộ một bí mật khủng khiếp cho ~Q~ thành viên thân cận. Tuy nhiên, các thành viên này lại có những người bạn trong IUH mà độ thân thiết còn hơn cả chủ nhiệm Rec, vì thế họ đã đi kể cho bạn của mình nghe (tất nhiên với yêu cầu giữ bí mật, đừng kể cho ai). Tiếc rằng bạn của họ lại đi lan truyền tiếp với tốc độ lan truyền là ~K~, cụ thể như sau:

Vào ngày đầu tiên, mỗi người biết bí mật sẽ kể cho tất cả những người quen trong ~K~ cấp, mỗi người sẽ kể với tất cả người quen của họ (cấp ~1~) rồi những người quen đó lại đi kể tiếp với những người quen khác (cấp ~2~), cứ thế cho đến cấp ~K~. Vào ngày thứ hai, tất cả người biết bí mật sẽ lại kể cho tất cả người quen trong trong ~2K~ cấp và cứ thế đến ngày thứ ~i~ là cấp ~iK~. Cho biết rằng ở IUH có tất cả ~N~ sinh viên được đánh số từ ~1,2,...,N~ và có tất cả ~M~ mối quan hệ bạn bè. Ngoài ra vì tính gắn kết nên bí mật trên đến một lúc nào đó sẽ lan ra toàn bộ các sinh viên, không ai là không biết.

Chủ nhiệm Rec sau khi biết thì rất tức giận nên đã chất vấn các thành viên trong buổi họp kín: với từng sinh viên trong trường, hãy cho biết bạn ấy biết được bí mật vào ngày thứ mấy?

Input

• Dòng đầu tiên ghi bốn số nguyên ~𝑁, 𝑀, 𝑄,𝐾~ với ~1 ≤ 𝑁, 𝑄,𝐾 ≤ 10^5~; ~𝑄 ≤ 𝑁~ và ~1 ≤ 𝑀 ≤ 2.10^5~.
• Dòng tiếp theo ghi ~𝑄~ số nguyên cho biết số thứ tự của các SV có trong buổi họp kín (coi như họ biết bí mật vào ngày thứ ~0~).
• Trong ~M~ dòng tiếp theo, mỗi dòng ghi một cặp số nguyên ~𝑢_𝑖~ và ~𝑣_𝑖~ biểu diễn STT của hai sinh viên quen nhau.

Output

• Ghi ra ~N~ số nguyên ở đó số nguyên thứ ~i~ là số ngày mà SV thứ ~i~ biết được bí mật.

Giới hạn:

• Ràng buộc 1: 30% số điểm có ~𝐾 = 1~; ~1 ≤ 𝑁;𝑄 ≤ 100~; ~1 ≤ 𝑀 ≤ 200~.
• Ràng buộc 2: 20% số điểm có ~1 ≤ 𝑁~; ~𝑄 ≤ 100~; ~1 ≤ 𝑀 ≤ 200~;
• Ràng buộc 3: 50% số điểm còn lại theo giả thiết của bài toán.

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