CF1870D.Prefix Purchase

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$.

你有一个长度为 $n$ 的数组 $a$，初始时所有元素均为零（即 $a_1 = a_2 = \ldots = a_n = 0$）。你还拥有一个长度为 $n$ 的整数数组 $c$。

初始时你有 $k$ 枚硬币。花费 $c_i$ 枚硬币，你可以将数组 $a$ 的前 $i$ 个元素各加 $1$（即对所有 $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$。

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$.

第一行包含一个整数 $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$。

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

对于每个测试用例，输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$ —— 可以得到的字典序最大的数组 $a$。

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

在第一个测试用例中，$a_1$ 不能大于 $5$；如果我们购买 $c_1$ 五次，资金将耗尽，因此 $a = [5, 0, 0]$。

在第二个测试用例中，$a_1$ 不能大于 $2$；但我们可各购买一次 $c_1$ 和 $c_2$（无法购买两次 $c_2$），因此 $a = [2, 1]$。