Codeforces Round 953 (Div. 2) |
---|
Закончено |
В Берляндии проходят выборы. На выборах участвуют $$$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$$$ победил.
53 12 0 32 30 105 35 4 3 2 14 53 10 7 16 02 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$$$ выиграет, если не допустить кандидата с номером $$$2$$$.
Название |
---|