← 返回题目列表

Codeforces · 1870/D

D. 前缀购买

中文机器翻译题面 查看原题

您有一个大小为 $$$n$$$ 的数组 $$$a$$$,最初用零填充 ($$$a_1 = a_2 = \ldots = a_n = 0$$$)。您还有一个大小为 $$$n$$$ 的整数数组 $$$c$$$。

最初,您有 $$$k$$$ 硬币。通过支付 $$$c_i$$$ 硬币,您可以将 $$$1$$$ 添加到数组 $$$a$$$ 的所有元素中,从第一个元素到第 $$$i$$$ 个元素(对于所有 $$$1 \leq j \leq i$$$,$$$a_j \mathrel{+}= 1$$$)。您可以多次购买任何$$$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$$$。

示例

输入 #1

4
3
1 2 3
5
2
3 4
7
3
3 2 1
2
6
10 6 4 6 3 4
7

输出 #1

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]$$$。