Bonus Distribution
Contest: Kotlin Heroes: Episode 3
Tags: *special, binary search, greedy, sortings

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$$$.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
0 0 1 0 
0 3 
134259259 121913582 121913582 621913577 
2 2 0 2 0 1 0 2 
1 0 0 0 0 0

Editorial:
At first, let's reorder array $$$a$$$ in such way that $$$a_i \ge a_{i + 1}$$$. Then the maximum among all $$$a_i + d_i$$$ is just a value $$$a_1 + d_1$$$.
In the first step, let's look at what is the maximum total bonus we can distribute if $$$d_1 = 0$$$ (so the $$$a_1 + d_1$$$ is the minimum possible). We can find the next formula: $$$d_i = a_1 - (i - 1) - a_i$$$ and the maximum possible bonus will be equal to $$$\sum{a_1 - (i - 1) - a_i}$$$.
If $$$k$$$ doesn't exceed the maximal bonus we can distribute if $$$d_1 = 0$$$ then the optimal answer is already found and we can greedily distribute bonus $$$k$$$: give to the first employe $$$0$$$, to the second $$$a_1 - 1 - a_2$$$ if we can (or all we have if we can't) and so on.
Otherwise, we need to increase $$$d_1$$$. But increasing $$$d_1$$$ by $$$1$$$ leads to increasing the maximal bonus by $$$n$$$. So, let's define $$$rem = k - \sum{a_1 - (i - 1) - a_i}$$$, and we can see that all we need to do is just give first $$$rem \mod n$$$ employees additional $$$\frac{rem}{n} + 1$$$ (or $$$d_i = d_i + \frac{rem}{n} + 1$$$) and other employes $$$\frac{rem}{n}$$$ (or $$$d_i = d_i + \frac{rem}{n}$$$).