D. Bonus Distribution time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputFor 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.InputThe 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.OutputPrint 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.ExampleInput
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
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 

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

0 0 1 0  0 3  134259259 121913582 121913582 621913577  2 2 0 2 0 1 0 2  1 0 0 0 0 0  
['*special problem', 'binary search', 'greedy', 'sortings']