Có ~n~ hộp kẹo được đánh số từ trái qua phải. Ban đầu hộp thứ ~i~ có ~a_i~ viên kẹo. Cần chia thêm ~m~ viên kẹo theo quy tắc: mỗi lần lấy một viên 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 thì chọn hộp bên trái nhất.

Yêu cầu

Xác định số kẹo ít nhất trong các hộp sau khi chia và lượng kẹo của từng hộp.

Input

Dòng đầu chứa hai số nguyên ~n,m~.

Dòng thứ hai chứa ~n~ số ~a_i~.

Output

Dòng đầu in số kẹo ít nhất trong các hộp sau khi chia.

Dòng thứ hai in ~n~ số là lượng kẹo của từng hộp sau khi chia.

Subtask

• 25% số điểm: ~m,n,a_i \le 10^3~.
• 25% số điểm: ~a_1=a_2=\ldots=a_n~, ~m,a_i \le 10^9~.
• 50% số điểm: ~n \le 10^5~, ~m \le 10^{16}~, ~a_i \le 10^{16}~.

Bài làm được 60% số điểm của mỗi test nếu dòng đầu tiên ghi đúng số kẹo ít nhất trong các hộp.

Ví dụ 1

5 3
6 2 4 2 3

3
6 4 4 3 3

Ví dụ 2

5 7
8 8 8 8 8

9
10 10 9 9 9