题面描述（简述）

• 给定数组$a$，删除任意元素需代价$k$，删除不超过$n−m$个后，取新数组前$m$项求和，总代价为 删除次数*$k$ + 前 $m$ 项和。
• 对每个 $m=1..n$，独立地从原数组出发，求最小代价。

思路

• 只需要在原数组前缀中删除。设最终新数组的第 $m$ 个元素在原数组中的位置为 $p$（$m$ ≤ $p$ ≤ $n$）。要让它成为新数组的第 $m$ 个，需要把前 $p$ 个元素中恰好删除 $p−m$ 个，后面的元素无需删除（删了也只会增加代价）。
• 为使前 $m$ 个保留元素的和值最小，应从前 $p$ 个元素里挑出值最小的 $m$ 个。
• 因此对给定 $p$，最小代价为:

题目内容

在小红书的推荐引擎中，为了评估用户行为序列的“权重”对内容分发的影响，平台将用户的一系列操作映射为一个长度为 $n$ 的数值数组$(a_1,a_2,…,a_n)$。

系统需要对前 $m$ 步行为进行聚合评估，但允许丢弃(删除)多达 $n-m$ 步“噪声”操作，每删除一步需支付权值 $k$ 的代价。

具体地，对于每个 $m(1≤m≤n)$ ，在原数组上最多执行 $n-m$ 次删除操作(删除任意位置的 $a_i$ ，结果不影响下次计算)，然后计算:

$删除次数*k+\sum^m_{i=1}a_i$

其中 $\sum^m_{i=1}a_i$ 是对删完后新数组的前 $m$ 项求和。

你需要对每一个 $m(1≤m≤n)$ 输出对应的最小代价。请注意，对于每个 $m$ 的计算都是独立的，每次都从完整的初始数组 $a$ 开始。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≤T≤50)$ 代表数据组数，每组测试数据描述如下:

第一行输入两个整数 $n,k(1≤n≤10^3,1≤k≤2*10^5)$,分别代表行为序列长度和删除代价。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≤a≤2*10^5)$ 表示原始行为权重。除此之外，保证单个测试文件的 $n$ 之和不超过 $10^3$ 。

输出描述

对于每个测试用例，新起一行输出 $n$ 个整数，第 $m$ 个数表示当保留前 $m$ 步行为时的最小代价，按 $m$ 从 $1$ 到 $n$ 顺序用空格分隔。

样例1

输入

1
3 1
4 2 3

输出

3 6 9