宫子从外面带来了$n$块布丁。这些布丁按$1$到$n$进行编号，其中第$i$块布丁的甜度为$a[i]$。

宫子非常喜欢吃布丁，但伊利亚不想让宫子这么快的吃完布丁。因此伊利亚规定宫子每天最多吃$m$块布丁，并且为了帮助宫子锻炼身体，伊利亚安排了惩罚机制。

如果宫子在第$d$天吃了若干块布丁，那么宫子需要做$y$（$y=$第$d$天吃的所有布丁的甜度总和 $* d$）个俯卧撑。

宫子不想做太多的俯卧撑，请你帮助她计算：如果宫子只吃$i$个布丁，她最少要做的俯卧撑总和为多少（从第1天到最后一天所做的俯卧撑总和）。

输入

第一行两个正整数$n$和$m$（n代表布丁的数量；$m$代表宫子每天最多吃几块布丁） $(1 \leq m \leq n \leq 200 000)$.

第二行$n$个正整数，第$i$个正整数$a[i]$代表第$i$个布丁的甜度.$(1\leq a[i] \leq 200 000)$

输出

一行$n$个正整数，第$i$个正整数$res[i]$代表如果宫子只吃$i$个布丁，她最少要做多少个俯卧撑。

9 2
6 19 3 4 4 2 6 7 8

2 5 11 18 30 43 62 83 121