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

У вас есть массив $$$a$$$ размера $$$n$$$, изначально заполненный нулями ($$$a_1 = a_2 = \ldots = a_n = 0$$$). Также у вас есть массив целых чисел $$$c$$$ размера $$$n$$$.

Изначально у вас есть $$$k$$$ монет. Заплатив $$$c_i$$$ монет, вы можете прибавить $$$1$$$ ко всем элементам массива $$$a$$$ с первого по $$$i$$$-й ($$$a_j \mathrel{+}= 1$$$ для всех $$$1 \leq j \leq i$$$). Покупать любое $$$c_i$$$ можно произвольное число раз. Покупка возможна только при $$$k \geq c_i$$$, то есть в любой момент должно выполняться $$$k \geq 0$$$.

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

Массив $$$a$$$ лексикографически меньше массива $$$b$$$ такой же длины, если и только если в первой позиции, где $$$a$$$ и $$$b$$$ различны, в массиве $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — размер массивов $$$a$$$ и $$$c$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$) — массив $$$c$$$.

Третья строка каждого набора входных данных содержит одно целое число $$$k$$$ ($$$1 \leq k \leq 10^9$$$) — количество монет, которое у вас есть.

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

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

На каждый набор входных данных выведите $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — лексикографически наибольший массив $$$a$$$, который можно получить.

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

В первом наборе входных данных $$$a_1$$$ не может быть больше $$$5$$$, а если пять раз купить $$$c_1$$$, то у нас не останется денег, поэтому $$$a = [5, 0, 0]$$$.

Во втором наборе входных данных $$$a_1$$$ не может быть больше $$$2$$$, при этом мы можем купить $$$c_1$$$ и $$$c_2$$$ по одному разу (купить $$$c_2$$$ дважды не получится), поэтому $$$a = [2, 1]$$$.