CF2254E.Chronostasis

Yousef has a hidden array $a$ of length $n$ consisting entirely of strictly positive integers.

An operation was performed exactly once to create an array $b$:

• Set $b_1 = a_1$.
• For every $i$ from $2$ to $n$, set $b_i = a_i - a_{i-1}$.
• After this, the elements of $b$ were completely shuffled.

You are given the shuffled array $b$. Reconstruct the lexicographically smallest original array $a$. If it's impossible for any arrangement of $b$ to produce an array $a$ of strictly positive integers, output $-1$.

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

恰好执行了一次如下操作来构造数组 $b$：

• 令 $b_1 = a_1$；
• 对每个从 $2$ 到 $n$ 的 $i$，令 $b_i = a_i - a_{i-1}$；
• 此后，数组 $b$ 的所有元素被完全打乱（即重排）。

你被给定打乱后的数组 $b$。请重构出字典序最小的原始数组 $a$。如果不存在任何 $b$ 的排列方式，使得由此生成的数组 $a$ 中所有元素均为严格正整数，则输出 $-1$。

The first line of input 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$ ($-10^9 \le b_i \le 10^9$) — the elements of the shuffled array $b$.

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$（$-10^9 \le b_i \le 10^9$）—— 表示被打乱顺序后的数组 $b$ 的元素。

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

For each test case, output $n$ strictly positive integers $a_1, a_2, \dots, a_n$ ($a_i \ge 1$) — the lexicographically smallest original array $a$. If it's impossible to create a valid array $a$, output $-1$ instead.

对于每个测试用例，输出 $n$ 个严格正整数 $a_1, a_2, \dots, a_n$（即 $a_i \ge 1$）——字典序最小的原始数组 $a$。如果无法构造出有效的数组 $a$，则输出 $-1$。

In the first test case, the only valid array is $a = [5]$.

In the second test case, there is no valid arrangement of the elements of $b$ that reconstructs an array $a$ consisting entirely of strictly positive integers. Therefore, the answer is $-1$.

In the third test case, one valid arrangement reconstructs the array $a=[1,1,3,2,6,3]$. The resulting sequence of differences $[1, 0, 2, -1, 4, -3]$ is a permutation of the given array $b$, and among all valid reconstructions, this array is lexicographically smallest.

在第一个测试用例中，唯一有效的数组是 $a = [5]$。

在第二个测试用例中，不存在一种对数组 $b$ 元素的有效排列方式，能够重构出一个完全由严格正整数组成的数组 $a$。因此答案为 $-1$。

在第三个测试用例中，一种有效的排列方式重构出数组 $a=[1,1,3,2,6,3]$。所得的差分序列 $[1, 0, 2, -1, 4, -3]$ 是给定数组 $b$ 的一个排列；而在所有有效的重构方案中，该数组是字典序最小的。