Tặng kẹo

Trong đợt thiện nguyện, ngoài các đồ dùng thiết yếu, đoàn còn chuẩn bị kẹo để gửi cho trẻ em vùng lũ. Đoàn đã chuẩn bị ~N~ hộp để đựng kẹo, các hộp được đánh số từ 1 đến ~N~. Ban đầu đoàn đã bỏ vào các hộp một số lượng kẹo, hộp thứ ~i~ có ~a[i]~ viên kẹo. Sau đó đoàn được nhận thêm ~M~ viên kẹo nữa nên quyết định bỏ thêm kẹo vào các hộp có sẵn. Để cho các hộp có số lượng kẹo tương đối đều nhau, các bạn trong đoàn bỏ thêm kẹo vào các hộp theo quy tắc sau: Mỗi lần lấy một viên kẹo trong số kẹo mới gửi đến bỏ vào hộp chứa ít kẹo nhất. Nếu có nhiều hộp như vậy thì đưa vào hộp có chỉ số nhỏ nhất. Quá trình này lặp lại cho tới khi hết ~M~ viên kẹo.

Yêu cầu: Xác định số lượng kẹo trong mỗi hộp sau khi phân chia hết ~M~ viên kẹo.

Dữ liệu vào:

Dòng đầu chứa hai số ~N~ và ~M~ (~0 ≤ N ≤ 10^5~; ~1 ≤ M ≤ 10^9~)

Dòng thứ hai chứa ~N~ số ~a_1, a_2, …, a_N~ ~(0 ≤ a_i ≤ 10^9)~

Kết quả: Một dòng duy nhất gồm ~N~ số, trong đó số thứ ~i~ là số kẹo trong hộp thứ ~i~ sau khi chia xong ~M~ viên kẹo.

Ví dụ:

Input:

4 4
2 1 4 2

Output:

3 3 4 3

Giới hạn:

50% số test có N ≤ 5000 và M ≤ 5000.