Вы стоите перед огромной лестницей, состоящей из $$$n$$$ ступенек. Ступеньки пронумерованы от нижней к верхней целыми числами от $$$1$$$ до $$$n$$$. Кроме того, будем считать, что пол, на котором вы стоите перед лестницей – это ступенька номер $$$0$$$.
Вы хотите забраться как можно выше, то есть на ступеньку с самым большим номером из возможных. Для этого у вас есть $$$x$$$ очков энергии и выбор из двух действий:
К сожалению, вы не знаете, сколько зарядов телепорта у вас осталось. Поэтому для каждого количества зарядов телепорта от $$$0$$$ до $$$n-1$$$ определите самую высокую ступеньку, на которую вы сможете подняться.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следует содержание наборов входных данных, каждый набор представлен в следующем формате.
Первая строка набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 300\,000; 1 \le x \le 10^{15}$$$) — количество ступенек в лестнице и изначальный запас очков энергии соответственно.
Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ равняется количеству очков энергии, которое необходимо потратить, чтобы забраться на $$$i$$$-ю ступеньку, находясь на ступеньке $$$i-1$$$.
Для каждого набора входных данных выведите ответ в отдельной строке в следующем формате.
В единственной строке выведите $$$n$$$ целых чисел $$$s_0, s_1, \dots, s_{n-1}$$$, где $$$s_i$$$ — номер самой высокой ступеньки, на которую вы сможете подняться, потратив не более $$$i$$$ зарядов телепорта.
34 510 11 15 1004 13371 10 100 10005 11000 1001 1002 1003 1004
0 1 2 34 4 4 40 1 2 3 4