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

В Берляндии проходят выборы. На выборах участвуют $$$n$$$ кандидатов, пронумерованных от $$$1$$$ до $$$n$$$. У $$$i$$$-го из них есть $$$a_i$$$ фанатов, которые проголосуют за него. Также дополнительно есть $$$c$$$ людей, которые не определились с любимым кандидатом, назовем их неопределившимися. Неопределившиеся люди проголосуют за кандидата с наименьшим номером.

На выборах побеждает кандидат, который набрал максимальное количество голосов, а если максимальное количество голосов набрали несколько кандидатов, то среди таких побеждает кандидат с наименьшим номером.

Такие выборы вам показались слишком скучными и предсказуемыми, поэтому вы решили не допустить некоторых кандидатов к ним. Если вы не допустите кандидата с номером $$$i$$$ к выборам, то все $$$a_i$$$ его фанатов станут неопределившимися, и на выборах проголосуют за допущенного кандидата с наименьшим номером.

Вам стало интересно узнать для каждого $$$i$$$ от $$$1$$$ до $$$n$$$, какое минимальное количество кандидатов надо не допустить к выборам, чтобы кандидат с номером $$$i$$$ выиграл выборы.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$c$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le c \le 10^9$$$) — количество кандидатов на выборах и количество неопределившихся людей.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — количество фанатов у каждого кандидата.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел, $$$i$$$-е из которых должно быть равно минимальному количеству кандидатов, которых нужно не допустить к выборам, чтобы кандидат с номером $$$i$$$ победил.

Пример
Входные данные
5
3 1
2 0 3
2 3
0 10
5 3
5 4 3 2 1
4 5
3 10 7 1
6 0
2 2 2 3 3 3
Выходные данные
0 1 2
1 0
0 1 2 3 4
1 0 2 3
1 1 2 0 4 5
Примечание

В первом наборе входных данных:

  • Если допустить всех кандидатов, то кандидат с номером $$$1$$$ наберёт $$$3$$$ голоса (за него проголосует $$$1$$$ неопределившийся человек), кандидат с номером $$$2$$$ наберёт $$$0$$$ голосов, кандидат с номером $$$3$$$ наберёт $$$3$$$ голоса. Таким образом, выиграет кандидат с номером $$$1$$$ (он набрал столько же голосов, сколько кандидат $$$3$$$, но его номер меньше), поэтому для него ответ равен $$$0$$$.
  • Если не допустить кандидата с номером $$$1$$$, то его $$$2$$$ фаната станут неопределившимися. Тогда кандидат с номером $$$2$$$ наберёт $$$3$$$ голоса (за него проголосуют $$$3$$$ неопределившихся человека) и кандидат с номером $$$3$$$ наберёт $$$3$$$ голоса. Таким образом, выиграет кандидат с номером $$$2$$$ (он набрал столько же голосов, сколько кандидат $$$3$$$, но его номер меньше), поэтому для него ответ равен $$$1$$$.
  • Если не допустить кандидатов с номерами $$$1$$$ и $$$2$$$, то выиграет кандидат с номером $$$3$$$, поэтому для него ответ равен $$$2$$$.

Во втором наборе входных данных кандидат с номером $$$1$$$ выиграет, если не допустить кандидата с номером $$$2$$$.