Các bạn học sinh trường THPT HVT chuẩn bị phân phát kẹo cho trẻ em nhân dịp tết trung thu. Các bạn đã chuẩn bị ~n~ hộp để đựng kẹo, các hộp được đánh số từ 1 đến ~n~. Ban đầu các bạn học sinh đã 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.

Ban đại diện Cha Mẹ học sinh của trường chuẩn bị thêm cho các em ~M~ viên kẹo và các học sinh trong nhóm quyết định đưa thêm kẹo vào các hộp. Để cho các hộp có số lượng kẹo tương đối đều nhau, các bạn quyết định 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ố các kẹo mà Ban đại diện Cha Mẹ học sinh chuẩn bị và 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 hết ~M~ viên kẹo.

Input

• Dòng đầu tiên chứa số nguyên dương ~N, M~ (~1 \le N \le 10^5, 1 \le M \le 10^9~);
• Dòng thứ 2 chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ (~0 \le a_i \le 10^9~).

Output

• Ghi 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.

Sample Input 1

4 5
2 1 4 2

Sample Output 1

4 3 4 3