Prefix Purchase
Contest: CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1800
Tags: greedy, implementation, sortings

You have an array $$$a$$$ of size $$$n$$$, initially filled with zeros ($$$a_1 = a_2 = \ldots = a_n = 0$$$). You also have an array of integers $$$c$$$ of size $$$n$$$.

Initially, you have $$$k$$$ coins. By paying $$$c_i$$$ coins, you can add $$$1$$$ to all elements of the array $$$a$$$ from the first to the $$$i$$$-th element ($$$a_j \mathrel{+}= 1$$$ for all $$$1 \leq j \leq i$$$). You can buy any $$$c_i$$$ any number of times. A purchase is only possible if $$$k \geq c_i$$$, meaning that at any moment $$$k \geq 0$$$ must hold true.

Find the lexicographically largest array $$$a$$$ that can be obtained.

An array $$$a$$$ is lexicographically smaller than an array $$$b$$$ of the same length if and only if in the first position where $$$a$$$ and $$$b$$$ differ, the element in array $$$a$$$ is smaller than the corresponding element in $$$b$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the size of arrays $$$a$$$ and $$$c$$$.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$) — the array $$$c$$$.

The third line of each test case contains a single integer $$$k$$$ ($$$1 \leq k \leq 10^9$$$) — the number of coins you have.

It is guaranteed that the sum of all $$$n$$$ values across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the lexicographically largest array $$$a$$$ that can be obtained.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$a_1$$$ cannot be greater than $$$5$$$, and if we buy $$$c_1$$$ five times, we will run out of money, so $$$a = [5, 0, 0]$$$.

In the second test case, $$$a_1$$$ cannot be greater than $$$2$$$, but we can buy $$$c_1$$$ and $$$c_2$$$ once each (buying $$$c_2$$$ twice is not possible), so $$$a = [2, 1]$$$.

Example input:
4
3
1 2 3
5
2
3 4
7
3
3 2 1
2
6
10 6 4 6 3 4
7

Example output:
5 0 0 
2 1 
2 2 2 
2 2 2 2 2 1

Editorial:
Note that if there is a prefix for which there is a longer prefix that costs less, then it is useless to buy the shorter prefix. All its purchases can be replaced with purchases of the longer prefix, and the answer will only improve. Therefore, we can replace each $$$c_i$$$ with the minimum $$$c_j$$$ among $$$i \leq j \leq n$$$ (the minimum price of a prefix of length at least $$$i$$$). After this, we will have $$$c_i \leq c_{i+1}$$$.
Now let's solve the problem greedily. We want to maximize the first element of the resulting array. It will be equal to $$$k / c_1$$$, since we cannot buy more prefixes of length $$$1$$$ ($$$c_1$$$ is the smallest price). After buying $$$k / c_1$$$ prefixes of length $$$1$$$, we will have some coins left. Now we can replace some purchases of $$$c_1$$$ with purchases of longer prefixes to improve the answer.
How much will it cost to replace $$$c_1$$$ with $$$c_i$$$? It will cost $$$c_i - c_1$$$ coins. Moreover, note that to replace $$$c_1$$$ with $$$c_i$$$, we can sequentially replace $$$c_1$$$ with $$$c_2$$$, $$$c_2$$$ with $$$c_3$$$, $$$\ldots$$$, $$$c_{i-1}$$$ with $$$c_i$$$ (since $$$c_1 \leq c_2 \leq \ldots \leq c_i$$$). This means that we can make only replacements of purchases of $$$c_{i-1}$$$ with purchases of $$$c_i$$$.
Let's say we have maximized the first $$$i-1$$$ elements of the answer, and we have $$$x$$$ coins left. Now we want to replace some purchases of $$$c_{i-1}$$$ with $$$c_i$$$. How many replacements can we make? We can afford to make no more than $$$\frac{x}{c_i - c_{i-1}}$$$ replacements (if $$$c_{i-1} = c_i$$$, then we can replace all $$$c_{i-1}$$$), and we cannot replace more purchases than we have made, so no more than $$$a_{i-1}$$$ replacements (this is the number of purchases of $$$c_{i-1}$$$). Therefore, $$$a_i = \min(a_{i-1}, \frac{x}{c_i - c_{i-1}})$$$, as we want to maximize $$$a_i$$$. Finally, subtract the cost of replacements from the number of coins and move on to $$$c_{i+1}$$$.