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

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #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