D. Распределение премий
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Впервые стартап Поликарпа закончил год с прибылью! Теперь он собирается распределить $$$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$$$.

Входные данные

В первой строке записано целое число $$$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$$$.

Выходные данные

Выведите ответы на $$$t$$$ заданных наборов входных данных в порядке их записи в тесте. Ответ выводите в виде последовательности неотрицательных целых чисел $$$d_1, d_2, \dots, d_n$$$. Если ответов несколько, то выведите любой из них.

Пример
Входные данные
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