7unar的榜单复原

背景

7unar 是社团 OJ 的管理员。某天服务器崩了，所有人的 AC 数全部丢失。

但万幸的是，数据库里还残留了一份「成就系统」的辅助数据——对于每个人，系统记录了一个值：所有 AC 数严格比他少的同学的 AC 数之和。

换句话说，设每个人的真实 AC 数为 $a_1, a_2, \ldots, a_n$，则残存数据 $b_i$ 定义为：

$$b_i = \sum_{a_j < a_i} a_j$$

现在 7unar 拿到了这 $n$ 个残存值 $b_1, b_2, \ldots, b_n$。请你复原出字典序最小的合法原始 AC 数序列 $a$（所有 $a_i$ 必须为正整数）。

如果没有任何合法方案，输出 $-1$。

题目描述

有一个由 $n$ 个正整数组成的隐藏数组 $a$。

对于每个元素 $a_i$，定义其「影子」$b_i$ 为数组中所有严格小于 $a_i$ 的元素之和。即：

$$b_i = \sum_{\substack{1 \le j \le n \\\\ a_j < a_i}} a_j$$

给定影子数组 $b$，请你还原出字典序最小的合法数组 $a$（所有 $a_i \ge 1$）。如果不存在，输出 $-1$。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^{4}$），表示测试数据组数。

每组测试数据：

• 第一行一个整数 $n$（$1 \le n \le 2 \times 10^{5}$），表示数组大小。

• 第二行 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i \le 2 \times 10^{14}$），表示影子数组。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^{5}$。

输出格式

对于每组测试数据：

• 如果存在合法方案，输出一行 $n$ 个整数，表示字典序最小的合法数组 $a$（$1 \le a_i \le 10^{18}$）。

• 否则输出 $-1$。

样例

8
1
0
5
0 4 0 4 14
3
4 0 0
3
0 0 0
3
0 1 1
4
1 1 1 1
7
0 4 4 4 4 4 9
5
0 0 0 3 3

1
2 5 2 5 6
3 2 2
1 1 1
1 2 2
-1
-1
1 1 1 2 2

样例解释

• 第一组：$n = 1$，没有更小的元素，所以 $b_1 = 0$。$a = [1]$ 合法且字典序最小。

• 第二组：$a = [2, 5, 2, 5, 6]$。两个 $2$ 没有更小的元素（$b = 0$）；每个 $5$ 有两个 $2$ 比它小（$b = 2 + 2 = 4$）；$6$ 有两个 $2$ 和两个 $5$ 比它小（$b = 2 + 2 + 5 + 5 = 14$）。

• 第三组：$a = [3, 2, 2]$。$3$ 有两个 $2$ 比它小（$b_1 = 2 + 2 = 4$）；两个 $2$ 没有更小的元素（$b_2 = b_3 = 0$）。

• 第四组：所有人 AC 数相同，没有严格小于关系，$b$ 全为 $0$。$a = [1, 1, 1]$ 字典序最小。

• 第五组：$b = [0, 1, 1]$。最小值为 $0$（对应 AC 数为 $1$），$b = 1$ 对应的元素必须大于 $1$，且严格小于它的元素只有那个 $1$，所以 $a = [1, 2, 2]$。

• 第六组：$b = [1, 1, 1, 1]$。没有 $b = 0$，意味着没有"最小值"，无解。

• 第七组：$b = [0, 4, 4, 4, 4, 4, 9]$。有五个人 $b = 4$，但 $b$ 的差值 $4 - 0 = 4$ 不能被人数 $1$ 整除……实际上 $9 - 4 = 5$ 不能被人数 $5$ 整除，无解。

数据范围

• $1 \le t \le 10^{4}$

• $1 \le n \le 2 \times 10^{5}$

• $0 \le b_i \le 2 \times 10^{14}$

• $\sum n \le 2 \times 10^{5}$