Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Вы стоите перед огромной лестницей, состоящей из $$$n$$$ ступенек. Ступеньки пронумерованы от нижней к верхней целыми числами от $$$1$$$ до $$$n$$$. Кроме того, будем считать, что пол, на котором вы стоите перед лестницей – это ступенька номер $$$0$$$.

Вы хотите забраться как можно выше, то есть на ступеньку с самым большим номером из возможных. Для этого у вас есть $$$x$$$ очков энергии и выбор из двух действий:

  1. Подняться на одну ступеньку выше. Чтобы подняться на $$$i$$$-ю ступеньку, находясь на ступеньке $$$i-1$$$, вам придётся потратить $$$a_i$$$ очков энергии. Если ваш текущий запас энергии меньше $$$a_i$$$, подняться (этим способом) на $$$i$$$-ю ступеньку вы не сможете;
  2. Телепортироваться ровно на одну ступеньку выше, не потратив очков энергии, но потратив ровно один заряд телепорта.

К сожалению, вы не знаете, сколько зарядов телепорта у вас осталось. Поэтому для каждого количества зарядов телепорта от $$$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$$$ зарядов телепорта.

Пример
Входные данные
3
4 5
10 11 15 100
4 1337
1 10 100 1000
5 1
1000 1001 1002 1003 1004
Выходные данные
0 1 2 3
4 4 4 4
0 1 2 3 4