CF2254D.Silhouette

Yousef has a secret array $a$ of $n$ strictly positive integers.

For each element $a_i$, its shadow $b_i$ is the sum of all elements in $a$ that are strictly smaller than $a_i$. Formally:

$$b\_i = \\sum\_{\\substack{1 \\le j \\le n\\\\ a\_j \\lt a\_i}} a\_j$$

You are given the shadow array $b$. Your task is to reconstruct the lexicographically smallest valid array $a$ consisting of strictly positive integers that satisfies the above condition. If no such array exists, output $-1$.

优素福有一个长度为 $n$ 的秘密数组 $a$，其中所有元素均为严格正整数。

对每个元素 $a_i$，其“影子” $b_i$ 定义为数组 $a$ 中所有严格小于 $a_i$ 的元素之和。形式化地：

$$b\_i = \\sum\_{\\substack{1 \\le j \\le n\\\\ a\_j \\lt a\_i}} a\_j$$

你被给定了影子数组 $b$。你的任务是重构出字典序最小的、由严格正整数组成的有效数组 $a$，使其满足上述条件。若不存在这样的数组，则输出 $-1$。

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array.

The second line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 2 \cdot 10^{14}$) — the shadow array.

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组的大小。

每个测试用例的第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \le b_i \le 2 \cdot 10^{14}$）——影子数组。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$) — the lexicographically smallest valid array $a$ that satisfies the condition. If no valid array exists, output $-1$ instead.

对于每个测试用例，输出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{18}$）——满足条件的字典序最小的有效数组 $a$。如果不存在有效数组，则输出 $-1$。

In the first test case, the answer is $a = [1]$. Since there is only one element, there are no strictly smaller elements, so its shadow is $0$. Thus $a=[1]$ is valid. It is also lexicographically smallest, because the only allowed values are positive integers, and $1$ is the smallest possible.

In the second test case, the answer is $a = [2,5,2,5,6]$:

• For each $2$, there is no smaller element in the array, so the shadow is $0$.
• For each $5$, the strictly smaller elements are the two $2$'s, so the shadow is $2+2=4$.
• For $6$, the strictly smaller elements are two $2$'s and two $5$'s, so the shadow is $2+2+5+5=14$.

Therefore the shadow array is exactly $b = [0,4,0,4,14]$.

In the third test case, the shadow array for $a = [3, 2, 2]$ is calculated as follows:

• For $a_1 = 3$, the strictly smaller elements in the array are the two $2$s. Their sum is $2 + 2 = 4$. So, $b_1 = 4$.
• For $a_2 = 2$, there are no strictly smaller elements in the array. So, $b_2 = 0$.
• For $a_3 = 2$, there are no strictly smaller elements in the array. So, $b_3 = 0$.

The resulting shadow array is $b = [4, 0, 0]$, which matches the input.

在第一个测试用例中，答案为 $a = [1]$。由于数组中仅有一个元素，因此不存在严格更小的元素，其阴影值为 $0$。因此 $a=[1]$ 是合法的。同时它也是字典序最小的，因为允许的取值仅为正整数，而 $1$ 是可能的最小值。

在第二个测试用例中，答案为 $a = [2,5,2,5,6]$：

• 对于每个 $2$，数组中不存在更小的元素，因此其阴影值为 $0$。
• 对于每个 $5$，数组中严格更小的元素是两个 $2$，因此其阴影值为 $2+2=4$。
• 对于 $6$，数组中严格更小的元素是两个 $2$ 和两个 $5$，因此其阴影值为 $2+2+5+5=14$。

因此得到的阴影数组恰好为 $b = [0,4,0,4,14]$。

在第三个测试用例中，对 $a = [3, 2, 2]$ 计算其阴影数组如下：

• 对于 $a_1 = 3$，数组中严格更小的元素是两个 $2$，它们的和为 $2 + 2 = 4$，故 $b_1 = 4$。
• 对于 $a_2 = 2$，数组中不存在严格更小的元素，故 $b_2 = 0$。
• 对于 $a_3 = 2$，数组中不存在严格更小的元素，故 $b_3 = 0$。

最终得到的阴影数组为 $b = [4, 0, 0]$，与输入一致。