310687: CF1870D. Prefix Purchase

D. Prefix Purchasetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

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

Output

5 0 0 
2 1 
2 2 2 
2 2 2 2 2 1 

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

题目大意：

存在一个大小为 $ n $ 的数组 $ a $，初始时所有元素都是 0 ($ a_1 = a_2 = \ldots = a_n = 0 $)。还有一个整数数组 $ c $，大小也为 $ n $。

最初，你有 $ k $ 枚硬币。通过支付 $ c_i $ 枚硬币，你可以将数组 $ a $ 从第一个到第 $ i $ 个元素的所有元素加 1 ($ a_j += 1 $ 对于所有 $ 1 \leq j \leq i $)。你可以购买任意 $ c_i $ 任意次数。只有当 $ k \geq c_i $ 时，购买才是可能的，这意味着在任何时刻 $ k \geq 0 $ 必须成立。

找出可以获得的字典序最大的数组 $ a $。

数组 $ a $ 字典序小于长度相同的数组 $ b $ 当且仅当在第一个不同的位置上，数组 $ a $ 中的元素小于数组 $ b $ 中相应的元素。

输入输出数据格式：

输入：

- 第一行包含一个整数 $ t $ ($ 1 \leq t \leq 10^4 $) —— 测试用例的数量。接下来是测试用例的描述。
- 每个测试用例的第一行包含一个整数 $ n $ ($ 1 \leq n \leq 2 \times 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 $ 个整数 $ a_1, a_2, \ldots, a_n $ —— 可以获得的字典序最大的数组 $ a $。题目大意： 存在一个大小为 $ n $ 的数组 $ a $，初始时所有元素都是 0 ($ a_1 = a_2 = \ldots = a_n = 0 $)。还有一个整数数组 $ c $，大小也为 $ n $。 最初，你有 $ k $ 枚硬币。通过支付 $ c_i $ 枚硬币，你可以将数组 $ a $ 从第一个到第 $ i $ 个元素的所有元素加 1 ($ a_j += 1 $ 对于所有 $ 1 \leq j \leq i $)。你可以购买任意 $ c_i $ 任意次数。只有当 $ k \geq c_i $ 时，购买才是可能的，这意味着在任何时刻 $ k \geq 0 $ 必须成立。 找出可以获得的字典序最大的数组 $ a $。 数组 $ a $ 字典序小于长度相同的数组 $ b $ 当且仅当在第一个不同的位置上，数组 $ a $ 中的元素小于数组 $ b $ 中相应的元素。 输入输出数据格式： 输入： - 第一行包含一个整数 $ t $ ($ 1 \leq t \leq 10^4 $) —— 测试用例的数量。接下来是测试用例的描述。 - 每个测试用例的第一行包含一个整数 $ n $ ($ 1 \leq n \leq 2 \times 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 $ 个整数 $ a_1, a_2, \ldots, a_n $ —— 可以获得的字典序最大的数组 $ a $。