← 返回题目列表

Codeforces · 1297/D

D. 奖金分配

中文机器翻译题面 查看原题

Polycarp 的初创公司首次在今年结束时实现盈利!现在他准备将$$$k$$$ burles 作为奖金分发给$$$n$$$ 员工。

已知第$$$i$$$员工当前工资为$$$a_i$$$,公司中所有$$$a_i$$$的值都不相同。

Polycarp 希望在 $$$n$$$ 员工之间分配 $$$k$$$ burles,因此本月第 $$$i$$$ 员工的工资将不是 $$$a_i$$$,而是 $$$a_i+d_i$$$($$$d_i \ge 0$$$,$$$d_i$$$ 是一个整数),其中$$$d_i$$$ 是第 $$$i$$$ 员工的奖金。当然,$$$d_1+d_2+\dots+d_n=k$$$。

Polycarp 将遵循两条规则来选择 $$$d_i$$$ 值:

- 工资的相对顺序不应改变:原工资最高的员工($$$a_i$$$为最高)在领取奖金后应获得最高的总付款($$$a_i+d_i$$$也是最高),原工资第二高的员工在领取奖金后应获得第二大的总付款,依此类推。
- 为了强调年度利润是团队的努力,Polycarp 希望最小化向员工支付的最大总付款(即最小化 $$$a_i+d_i$$$ 的最大值)。

帮助Polycarp决定非负整数奖金$$$d_i$$$,使得:

- 他们的总和是 $$$k$$$,
- 对于每个员工,收到严格多于他们的人数保持不变(也就是说,如果您按 $$$a_i$$$ 和 $$$a_i+d_i$$$ 对员工进行排序,您会得到相同的员工顺序),
- 所有 $$$a_i + d_i$$$ 都不同,
- $$$a_i+d_i$$$ 值的最大值是可能的最小值。

帮助 Polycarp 并打印任何可能的答案 $$$d_1, d_2, \dots, d_n$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 10^9$$$) — 员工数量和奖金总额。

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 员工的当前工资。

保证输入中所有 $$$n$$$ 值的总和不超过 $$$10^5$$$。

输出

按照 $$$t$$$ 测试用例在输入中出现的顺序打印答案。将每个答案打印为非负整数 $$$d_1, d_2, \dots, d_n$$$ 序列。如果有多个答案,请打印其中任何一个。

示例

输入 #1

5
4 1
3 1 4 2
2 3
10 2
4 1000000000
987654321 1000000000 999999999 500000000
8 9
5 6 1 8 3 4 2 7
6 1
6 3 1 8 5 9

输出 #1

0 0 1 0 
0 3 
134259259 121913582 121913582 621913577 
2 2 0 2 0 1 0 2 
1 0 0 0 0 0