CF1297D Bonus Distribution

Polycarp 的初创公司第一次在年终实现盈利！他希望把 $ k $ 个布尔作为奖金发放给 $ n $ 名员工。 当前，每位员工的薪水是互不相同的，具体为第 $ i $ 名员工的薪水为 $ a_i $。 Polycarp 计划在不改变员工相对薪水顺序的情况下，将 $ k $ 个布尔分给 $ n $ 名员工，也就是说，每位员工的最终薪水应该是 $ a_i+d_i $ 其中 $ d_i\ge 0 $ 且 $ d_i $ 是整数。同时，保证分配的总奖金数 $ d_1 + d_2 + \dots + d_n = k $。 Polycarp 遵循以下原则来分配奖金： - 保持薪水的相对高低顺序不变：原本薪水最高的员工，在发放奖金后依然要保持最高，其次是薪水第二高的依次类推。 - 为了体现团队的集体努力成果，Polycarp 想要尽量使员工最终薪水的最高值最小化。 请帮助 Polycarp 确定各个员工的奖金 $ d_i $，以满足： - 所有员工的奖金总和为 $ k $， - 每个员工在所有人中的相对薪水排名不变， - 最终薪水即 $ a_i + d_i $ 互不相同， - 从而令最大值最小化。 请输出 $ 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 $），表示每位员工当前的薪水。 保证所有测试用例中员工数量 $ n $ 的总和不超过 $ 10^5 $。

按照输入的顺序输出各个测试用例的答案。每个答案应为一个非负整数序列 $ d_1, d_2, \dots, d_n $。如果有多种可能的组合，输出任意一个即可。 **本翻译由 AI 自动生成**