对于 $(1, 2, \dots, M)$ 的一个排列 $(Q_1, Q_2, \dots, Q_M)$，我们定义一个长度为 $M-1$ 的序列 $f(Q)$ 如下：

• 初始化一个长度为 $M-1$ 的序列 $X = (0, 0, \dots, 0)$。
• 执行以下操作 $M-1$ 次：
  • 对于 $i = 1, 2, \dots, M-1$，执行以下操作：
    • 如果 $Q_i > Q_{i+1}$，交换 $Q_i$ 和 $Q_{i+1}$，并将 $X_i$ 加 1。
    • 如果 $Q_i < Q_{i+1}$，则不进行任何操作。
• 最终的序列 $X$ 即为 $f(Q)$。

给定一个长度为 $N-1$ 的序列 $B = (B_1, B_2, \dots, B_{N-1})$。请确定是否存在一个 $(1, 2, \dots, N)$ 的排列 $P$，使得 $f(P) = B$。如果存在，请找出字典序最小的那个排列。

你需要处理 $T$ 组测试数据。

输入格式

输入通过标准输入给出，格式如下：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例的格式如下：

$N$ $B_1 \ B_2 \ \dots \ B_{N-1}$

• $1 \le T \le 1.5 \times 10^5$
• $2 \le N \le 3 \times 10^5$
• $0 \le B_i \le N-1$ ($i = 1, 2, \dots, N-1$)
• 所有测试用例的 $N$ 之和不超过 $3 \times 10^5$。
• 所有输入值均为整数。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。

如果不存在满足条件的排列，输出 -1。否则，输出满足条件的字典序最小的排列。

样例

样例输入 1

3
4
2 1 1
5
2 0 2 4
6
2 3 2 1 1

样例输出 1

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

说明

在第一个测试用例中，当 $P = (3, 2, 4, 1)$ 时，$f(P)$ 的计算过程如下：

• 起初，$X = (0, 0, 0)$。
• 第一次操作执行如下：
  • 由于 $P_1 > P_2$，交换 $P_1$ 和 $P_2$，并将 $X_1$ 加 1。
    • 结果为 $X = (1, 0, 0)$ 且 $P = (2, 3, 4, 1)$。
  • 由于 $P_2 < P_3$，不进行任何操作。
  • 由于 $P_3 > P_4$，交换 $P_3$ 和 $P_4$，并将 $X_3$ 加 1。
    • 结果为 $X = (1, 0, 1)$ 且 $P = (2, 3, 1, 4)$。
• 第二次操作执行如下：
  • 由于 $P_1 < P_2$，不进行任何操作。
  • 由于 $P_2 > P_3$，交换 $P_2$ 和 $P_3$，并将 $X_2$ 加 1。
    • 结果为 $X = (1, 1, 1)$ 且 $P = (2, 1, 3, 4)$。
  • 由于 $P_3 < P_4$，不进行任何操作。
• 第三次操作执行如下：
  • 由于 $P_1 > P_2$，交换 $P_1$ 和 $P_2$，并将 $X_1$ 加 1。
    • 结果为 $X = (2, 1, 1)$ 且 $P = (1, 2, 3, 4)$。
  • 由于 $P_2 < P_3$，不进行任何操作。
  • 由于 $P_3 < P_4$，不进行任何操作。

因此，$f(P) = (2, 1, 1)$。特别地，该 $P$ 是满足 $f(P) = B$ 的字典序最小的排列。

在第二个测试用例中，不存在满足 $f(P) = (2, 0, 2, 4)$ 的排列 $P$。