Nhân dịp Tết thiếu nhi, các bạn tỉnh nguyện viên chuẩn bị n hộp để đựng kẹo. Các hộp được đánh số ~1,2,3,..., n~ từ trái qua phải. Ban đầu, hộp thứ ~i~ có ~a_i~ viên.

Ban tổ chức tặng thêm ~m~ viên kẹo và các tỉnh nguyện viên muốn chia số kẹo này vào các hộp sao cho sau khi chia kẹo, số kẹo ở hộp ít nhất là lớn nhất có thể. Cách chia kẹo như sau:

• Mỗi lần lẩy ~1~ viên kẹo và bỏ vào hộp có ít kẹo nhất.
• Nếu có nhiều hộp cùng ít kẹo nhất, chọn hộp có số hiệu nhỏ nhất (bên trái nhất).
• Lặp lại cho đến khi chia hết ~m~ viên kẹo.

Yêu cầu: Hãy xác định số kẹo từng hộp sau khi chia hết số kẹo đó.

Input

Dòng đầu tiên chứa hai số nguyên ~n,m~ (~n ≤ 10^4~, ~m ≤ 10^{16}~)

Dòng thứ hai chứa ~n~ số tự nhiên ~a_1, a_2, ..., a_n~ là số lượng kẹo ban đầu trong mỗi hộp (~a_i \le 10^{16}~).

Output

Dòng dầu tiên ghi số lượng kẹo của hộp ít nhất sau khi thực hiện chia hết ~m~ viên kẹo.

Dòng thứ hai là ~n~ số ~b_1, b_2, b_3 ..., b_n~ với ~b_i~ là số lượng kẹo trong hộp ~i~ sau khi thực hiện chia kẹo.

Sample Input 1

5 3
6 2 4 2 3

Sample Output 1

3
6 4 4 3 3

Dãy ban đầu: ~(6,2,4,2,3)~

• Lượt ~1~: thêm ~1~ viên vào hộp ~2~: ~(6,3,4,2,3)~
• Lượt ~2~: thêm ~1~ viên vào hộp ~4~: ~(6,3,4,3,3)~
• Lượt ~3~: thêm ~1~ viên vào hộp ~2~: ~(6,4,4,3,3)~

Sample Input 2

5 7
8 8 8 8 8

Sample Output 2

9 
10 10 9 9 9

Subtasks

Bài làm của thí sinh sẽ được ~60 \%~ số điểm của test nếu như chi đưa ra đúng số lượng kẹo nhỏ nhất trong các hộp.