Có ~n~ chiếc hộp đánh số từ 1 đến ~n~ để đựng kẹo; ban đầu hộp thứ ~i~ có ~a_i~ viên kẹo. Người ta chuẩn bị thêm ~m~ viên kẹo nữa để bỏ vào các hộp sao cho số kẹo giữa các hộp tương đối đều nhau, theo quy tắc sau: mỗi lần lấy một viên kẹo trong số ~m~ viên đó và bỏ vào hộp đang có ít kẹo nhất; nếu có nhiều hộp cùng ít kẹo nhất thì chọn hộp có chỉ số nhỏ nhất. Lặp lại cho đến khi bỏ hết ~m~ viên kẹo.

Hãy xác định số kẹo trong mỗi hộp sau khi đã bỏ hết ~m~ viên.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~1 \le n \le 10^5, 1 \le m \le 10^9~) là số hộp và số viên kẹo thêm vào.
• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^9~).

Kết quả

Ghi ra một dòng gồm ~n~ số, số thứ ~i~ là số kẹo trong hộp thứ ~i~ sau khi chia xong ~m~ viên kẹo.

Ví dụ

CANDY.INP

4 5
2 1 4 2

CANDY.OUT

4 3 4 3

Giải thích: Lần lượt kẹo vào hộp 2 (thành 2), hộp 1 (thành 3), hộp 2 (thành 3), hộp 4 (thành 3), rồi hộp 1 (thành 4); kết quả 4 3 4 3.

Giới hạn

• Subtask 1 (50% số điểm): ~n, m \le 5 \times 10^3~.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.