//2024.4.4
//https://www.acwing.com/file_system/file/content/whole/index/content/10768190/
//https://www.lanqiao.cn/problems/3515/learning/
//整数删除
/*
【主干思路】:【我们需要解决两个问题:1、如何动态的找到最小值(使用“堆”解决) 2、如何给最小值两边的值加上该最小值的数值(双向链表)】
【解释】:由于要进行大量的删除操作, 不难想到可以使用链表.
而本题需要动态的求最小值, 显然可以使用堆.
每次从堆中取出最小值的下标, 然后在链表中删除它.
但本题特殊点在于将其删除。并把与它相邻的整数加上被删除的数值, 所以会导致还在堆中的元素的权的变化.
我们可以注意到, 每次删除操作只会让一些元素变大, 而不会让元素变小. 也就是, 可能会让原本的最小值变成不是最小值.
因此我们取出堆中的最小值时, 需要将此元素的排序权和实际的值进行对比, 如果实际的值变大了, 则当前元素并不一定是最小值, 需要重新放回堆中.
*/
#pragma GCC target ("avx")
#pragma GCC optimize (2, 3, "Ofast", "inline", "-ffast-math")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_cxx;
using ll = long long;
typedef pair<int, int> PII;
const int N = 5e5 + 10;
// v <下标>:v[i]存的是数值,i是下标
// l <左边相连元素的地址>
// r <右边相连的地址>
ll v[N], l[N], r[N];
void del(int x) {
r[l[x]] = r[x], l[r[x]] = l[x];
v[l[x]] += v[x], v[r[x]] += v[x];
}
signed main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
//初始化双链表
r[0] = 1, l[n + 1] = n;
//优先队列,这里是小根堆
priority_queue<PII, vector<PII>, greater<PII>> h;
for (int i = 1; i <= n; i ++){
cin >> v[i];
l[i] = i - 1;
r[i] = i + 1;
h.push({v[i], i});
}
while (k --) {
auto p = h.top(); //取出最小值
h.pop();//弹出堆顶元素
if (p.first != v[p.second]){//这里意思是i所指向的v[i]已经不是当初存入堆的那个v[i]了,v[i]已经发生了变化了。而且这道题中的v[i]一定是变大了
h.push({v[p.second], p.second});//将新的v[i]存入堆中
k ++;//对应上面while循环的k--
}
else del(p.second);//否则就将这个最小值删除,并将其两端的数都加上v[i]这个最小值
}
//输出最后留下的所有数。注意:我们是用链表存的,所以需要用链表的方式去遍历
int head = r[0];
while (head != n + 1) {
cout << v[head]<< " ";
head = r[head];
}
return 0;
}