CF1297D.Bonus Distribution

For the first time, Polycarp's startup ended the year with a profit! Now he is about to distribute $k$ burles as a bonus among $n$ employees.

It is known that the current salary of the $i$-th employee is $a_i$ and all the values of $a_i$ in the company are different.

Polycarp wants to distribute the $k$ burles between $n$ employees so this month the $i$-th employee will be paid not $a_i$, but $a_i+d_i$ ($d_i \ge 0$, $d_i$ is an integer), where $d_i$ is the bonus for the $i$-th employee. Of course, $d_1+d_2+\dots+d_n=k$.

Polycarp will follow two rules for choosing the values $d_i$:

• the relative order of the salaries should not be changed: the employee with originally the highest salary ($a_i$ is the maximum) should have the highest total payment after receiving their bonus ($a_i+d_i$ is also the maximum), the employee whose salary was originally the second-largest should receive the second-largest total payment after receiving their bonus and so on.
• to emphasize that annual profit is a group effort, Polycarp wants to minimize the maximum total payment to an employee (i.e minimize the maximum value of $a_i+d_i$).

Help Polycarp decide the non-negative integer bonuses $d_i$ such that:

• their sum is $k$,
• for each employee, the number of those who receive strictly more than them remains unchanged (that is, if you sort employees by $a_i$ and by $a_i+d_i$, you get the same order of employees),
• all $a_i + d_i$ are different,
• the maximum of the values $a_i+d_i$ is the minimum possible.

Help Polycarp and print any of the possible answers $d_1, d_2, \dots, d_n$.

波利卡普的创业公司首次实现了年度盈利！现在他计划将 $k$ 卢布作为奖金分配给 $n$ 名员工。

已知第 $i$ 名员工当前的工资为 $a_i$，且公司中所有 $a_i$ 的值互不相同。

波利卡普希望将 $k$ 卢布在 $n$ 名员工之间分配，使得本月第 $i$ 名员工实际获得的薪酬不再是 $a_i$，而是 $a_i+d_i$（其中 $d_i \ge 0$，且 $d_i$ 为整数），$d_i$ 即为分配给第 $i$ 名员工的奖金。显然，必须满足 $d_1+d_2+\dots+d_n=k$。

波利卡普在确定 $d_i$ 的取值时将遵循两条规则：

• 不得改变工资的相对顺序：原本工资最高者（即 $a_i$ 为最大值者）在获得奖金后总薪酬也必须最高（即 $a_i+d_i$ 也为最大值）；原本工资排名第二者，在获得奖金后总薪酬也必须排名第二；依此类推。
• 强调年度盈利是集体努力的结果，波利卡普希望最小化单名员工所能获得的最高总薪酬（即最小化所有 $a_i+d_i$ 中的最大值）。

请帮助波利卡普确定一组非负整数奖金 $d_i$，使其满足：

• 总和为 $k$；
• 对每名员工而言，薪酬严格高于其的人数保持不变（即：若按 $a_i$ 排序员工，与按 $a_i+d_i$ 排序员工，所得员工顺序完全一致）；
• 所有 $a_i + d_i$ 互不相同；
• $a_i+d_i$ 的最大值尽可能小。

请帮助波利卡普，并输出任意一组满足条件的解 $d_1, d_2, \dots, d_n$。

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \le k \le 10^9$) — the number of employees and the total bonus.

The second line of each test case contains $n$ different integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the current salary of the $i$-th employee.

It is guaranteed that the sum of all $n$ values in the input does not exceed $10^5$.

第一行包含一个整数 $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$。

Print the answers to $t$ test cases in the order they appear in the input. Print each answer as a sequence of non-negative integers $d_1, d_2, \dots, d_n$. If there are several answers, print any of them.

按输入中出现的顺序输出 $t$ 个测试用例的答案。每个答案输出为一串非负整数 $d_1, d_2, \dots, d_n$。若存在多个可行答案，输出任意一个即可。