您有一个大小为 $$$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]$$$。