An muốn thực hiện quá trình xây dựng và tính toán trên một dãy số ~B~ không giảm như sau:

• Bắt đầu từ dãy rỗng, thực hiện ~n~ bước thêm phần tử vào dãy, số được thêm ở bước thứ ~i~ ~(1 \le i \le n)~ là ~a_i~.

• Ở mỗi bước, sau khi thêm phần tử, sắp xếp lại dãy theo thứ tự không giảm và tính tổng các phần tử có chỉ số ~1, k+1, 2k+1, 3k+1, \dots~ (chỉ số các phần tử của dãy bắt đầu từ ~1~, ~k~ là số nguyên dương cho trước).

Hãy giúp An kiểm định công việc của cậu ấy bằng cách viết chương trình tính toán tổng thu được sau mỗi bước.

Input

• Dòng 1: hai số nguyên ~n, k~ ~(1 \le k \le n \le 10^5)~;

• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

Dòng ~1 \dots n~: dòng ~i~ ghi số nguyên là tổng tính được sau khi thêm phần tử ~a_i~.

Scoring

Sample Input 1

6 3
5 6 1 1 4 7

Sample Output 1

5
5
1
7
6
6

Notes

• Thêm ~5~: dãy là ~[5]~, tổng bằng ~5~;

• Thêm ~6~: dãy là ~[5,6]~, tổng bằng ~5~;

• Thêm ~1~: dãy là ~[1,5,6]~, tổng bằng ~1~;

• Thêm ~1~: dãy là ~[1,1,5,6]~, tổng bằng ~7~;

• Thêm ~4~: dãy là ~[1,1,4,5,6]~, tổng bằng ~6~;

• Thêm ~7~: dãy là ~[1,1,4,5,6,7]~, tổng bằng ~6~.