Ăn kẹo

Cho $n$ chiếc kẹo được đánh số từ $1$ đến $n$. Chiếc kẹo thứ $i$ có độ ngọt là một số nguyên $a_i$.

Bạn có thể ăn nhiều nhất $m$ chiếc kẹo mỗi ngày. Các ngày được đánh số $1,2,3,\dots$. Nếu bạn ăn chiếc kẹo $i$ vào ngày thứ $d$, bạn phải chịu một lượng đường phạt bằng $d·a_i$ (kẹo càng để lâu càng ngọt). Mỗi chiếc kẹo chỉ được ăn nhiều nhất một lần.

Tổng lượng đường phạt là tổng các giá trị phạt của tất cả các chiếc kẹo đã ăn.

Với mỗi $k$ từ $1$ đến $n$, bạn cần tìm tổng lượng đường phạt nhỏ nhất nếu phải ăn đúng $k$ chiếc kẹo (được chọn và sắp xếp tuỳ ý theo các ngày).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ ($1\le m\le n\le 200000$).
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 200000$).

Dữ liệu ra

In ra trên cùng một dòng $n$ số nguyên $x_1,x_2,\dots ,x_n$, cách nhau bởi dấu cách, trong đó $x_k$ là tổng lượng đường phạt nhỏ nhất khi ăn đúng $k$ chiếc kẹo.

Ràng buộc

• $1\le m\le n\le 200000$
• $1\le a_i\le 200000$

Ví dụ