Nhân dịp Tết thiếu nhi ngày 1-6, Công đoàn của công ty VHP sẽ tổ chức phát quà cho các con của cán bộ công nhân viên trong công ty có thành tích học tập tốt. Họ muốn phát ~k~ phần quà, mỗi phần quà đều có một bó hoa, một hộp bút, một quyển vở. Hiện tại, Công đoàn đã chuẩn bị được: ~a~ bó hoa, ~b~ hộp bút, ~c~ quyển vở.

Yêu cầu: Tính số lượng tối thiểu các món đồ mà Công đoàn cần chuẩn bị thêm để đảm bảo có đủ ~k~ phần quà.

Input

Một dòng gồm bốn số nguyên ~a~, ~b~, ~c~, ~k~ (~1 \le a, b, c, k \le 1000~) tương ứng là số bó hoa, số hộp bút, số quyển vở, số phần quà.

Output

Một số nguyên duy nhất là số món đồ cần chuẩn bị thêm.

Sample Input 1

2 3 5 4

Sample Output 1

3

• Có 2 bó hoa, 3 hộp bút, 5 quyển vở nên chúng ta có 2 phần quà.
• Chúng ta cần có thêm 2 bó hoa, 1 hộp bút nữa để tổng số là 4 phần quà.
• Số món đồ cần chuẩn bị thêm là: ~2+1=3~.

Gần nhà Bờm có một ga tàu điện. Tại ga này, hàng ngày, chuyến tàu điện đầu tiên sẽ dừng đón khách tại thời điểm ~T_0~, chuyến thứ hai dừng đón khách tại thời điểm ~T_0+D~, chuyến thứ ba dừng tại thời điểm ~T_0+2 \times D,...~ Có ~N~ hành khách thường xuyên chờ tàu điện tại ga. Hành khách thứ ~i~ đến ga tàu tại thời điểm ~s_i~ và sẽ lên chuyến tàu đầu tiên đến ga ở thời điểm không sớm hơn ~s_i~.

Yêu cầu: Cho ~T_0~, ~D~ và thời điểm các hành khách đến ga. Hãy xác định số hiệu chuyến tàu điện của từng hành khách sẽ lên, giả sử thời gian lên xuống xe của mỗi hành khách là không đáng kể.

Input

Dòng thứ nhất chứa ba số nguyên ~N~, ~D~, ~T_0~ (~2 \le N \le 10^4~; ~1 \le D \le 10^4~; ~0 \le T_0 \le 10^5~). Dòng thứ hai chứa ~N~ số nguyên ~s_1, s_2, ..., s_N~ (~0 \le s_i \le 10^6~).

Output

Gồm một dòng chứa ~N~ số nguyên, số thứ ~i~ là số hiệu chuyến tàu điện mà hành khách thứ ~i~ sẽ lên.

Sample Input 1

3 5 8
0 15 23

Sample Output 1

1 3 4

Giải thích:

• Hành khách đầu tiên đón được chuyến tàu thứ 1 ở thời điểm 8.
• Hành khách thứ 2 đón được chuyến tàu thứ 3 ở thời điểm 18.
• Hành khách thứ 3 đón được chuyến tàu thứ 4 ở thời điểm 23.

Nhân dịp Tết thiếu nhi ngày 1-6, Công đoàn của công ty VHP sẽ tổ chức phát quà cho các con của cán bộ công nhân viên trong công ty có thành tích học tập tốt. Họ muốn phát ~k~ phần quà. Mỗi phần quà đều có một bó hoa, một hộp bút, một quyển vở. Hiện tại, Công đoàn đã chuẩn bị được:

• ~a~ bó hoa,
• ~b~ hộp bút,
• ~c~ quyển vở.

Yêu cầu: Tính số lượng tối thiểu các món đồ mà Công đoàn cần chuẩn bị thêm để đảm bảo có đủ ~k~ phần quà.

Input

• Một dòng gồm bốn số nguyên ~a, b, c, k~ (~1 \le a, b, c, k \le 1000~) tương ứng là số bó hoa, số hộp bút, số quyển vở, số phần quà.

Output

• Một số nguyên duy nhất là số món đồ cần chuẩn bị thêm.

Sample Input 1

2 3 5 4

Sample Output 1

3

Gần nhà Bờm có một ga tàu điện. Tại ga này, hàng ngày, chuyến tàu đầu tiên sẽ dừng đón khách tại thời điểm ~T_0~, chuyến thứ hai dừng đón khách tại thời điểm ~T_0 + D~, chuyến thứ ba dừng tại thời điểm ~T_0 + 2 \times D~, ... Có ~N~ hành khách thường xuyên chờ tàu điện tại ga. Hành khách thứ ~i~ đến ga tàu tại thời điểm ~s_i~ và sẽ lên chuyến tàu đầu tiên đến ga ở thời điểm không sớm hơn ~s_i~.

Yêu cầu: Xác định số hiệu chuyến tàu điện của từng hành khách sẽ lên, giả sử thời gian lên xuống xe của mỗi hành khách là không đáng kể.

Input

• Dòng thứ nhất chứa ba số nguyên ~N, D, T_0~ (~2 \le N \le 10^4~; ~1 \le D \le 10^4~; ~0 \le T_0 \le 10^5~);
• Dòng thứ hai chứa ~N~ số nguyên ~s_1, s_2, \dots, s_N~ (~0 \le s_i \le 10^6~).

Output

• Gồm một dòng chứa ~N~ số nguyên, số thứ ~i~ là số hiệu chuyến tàu điện mà hành khách thứ ~i~ sẽ lên.

Sample Input 1

3 5 8 0 15 23

Sample Output 1

1 3 4